题目大意:给你n个点,m条可选的有向边,要你选择n-1条边使得一号点可以到达所有点且边权最小,求最小的边权是多少 n<=100 m<=10000
这题就是一个裸的最小树形图(朱刘算法),不多说了,直接贴代码
#include<cmath> #include<cstdio> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #define sqr(x) ((x)*(x)) using namespace std; const int maxn=110,maxm=10011; const double INF=1e9; struct Tedge{int x,y; double w;}e[maxm]; int n,m; double x[maxn],y[maxn]; double dis(int a,int b){return sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b]));} void init(){ for (int i=1;i<=n;++i) scanf("%lf%lf",x+i,y+i); for (int i=1;i<=m;++i){ scanf("%d%d",&e[i].x,&e[i].y); e[i].w=dis(e[i].x,e[i].y); if (e[i].x==e[i].y) --i,--m; } } double in[maxn]; int pre[maxn],vis[maxn],be[maxn]; void work(){ int V=n,E=m,root=1; double ans=0; while (1){ for (int i=1;i<=V;++i) in[i]=INF,pre[i]=0; for (int i=1;i<=E;++i) if (e[i].x!=e[i].y && in[e[i].y]>e[i].w) in[e[i].y]=e[i].w,pre[e[i].y]=e[i].x; for (int i=1;i<=V;++i) if (i!=root && !pre[i]) return puts("poor snoopy"),void(); int cnt=0; for (int i=1;i<=V;++i) vis[i]=be[i]=0; in[root]=0; for (int i=1;i<=V;++i){ ans+=in[i]; int tmp=i,t; while (vis[tmp]!=i && !be[tmp] && tmp!=root) vis[tmp]=i,tmp=pre[tmp]; if (tmp!=root && !be[tmp]) for (be[tmp]=++cnt,t=pre[tmp];t!=tmp;t=pre[t]) be[t]=cnt; } if (!cnt) return printf("%.2f\n",ans),void(); for (int i=1;i<=V;++i) if (!be[i]) be[i]=++cnt; for (int i=1;i<=E;++i){ int x=e[i].x,y=e[i].y; if ((e[i].x=be[x])!=(e[i].y=be[y])) e[i].w-=in[y]; } root=be[root]; V=cnt; } } int main(){while (scanf("%d%d",&n,&m)!=EOF) init(),work(); return 0;}
。。。上面的那个是有一定的问题的,可能会被卡到O(n^3+nm)的,下面再给出一个修改过后是严格O(n^2+nm)的
#include<cmath> #include<cstdio> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #define sqr(x) ((x)*(x)) using namespace std; const int maxn=110,maxm=10011,INF=(int)1e9; struct Tedge{int x,y; double w;}e[maxm]; int n,m; double x[maxn],y[maxn]; double dis(int a,int b){return sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b]));} void init(){ for (int i=1;i<=n;++i) scanf("%lf%lf",x+i,y+i); for (int i=1;i<=m;++i){ scanf("%d%d",&e[i].x,&e[i].y); e[i].w=dis(e[i].x,e[i].y); if (e[i].x==e[i].y) --i,--m; } } double in[maxn];int pre[maxn],be[maxn],vis[maxn]; void work(){ int V=n,E=m,root=1; double ans=0; while (1){ for (int i=1;i<=V;++i) in[i]=INF; in[root]=0; int cnt=0,ne=0; for (int i=1;i<=E;++i) if (e[i].y!=root && in[e[i].y]>e[i].w) in[e[i].y]=e[i].w,pre[e[i].y]=e[i].x; for (int i=1;i<=V;++i) if (in[i]==INF) return puts("poor snoopy"),void(); for (int i=1;i<=V;++i) be[i]=vis[i]=0; vis[root]=V+1; for (int i=1;i<=V;++i){ ans+=in[i]; int tmp=i,t; while (!vis[tmp]) vis[tmp]=i,tmp=pre[tmp]; if (vis[tmp]==i) for (be[tmp]=++cnt,t=pre[tmp];t!=tmp;t=pre[t]) be[t]=cnt; } if (!cnt) return printf("%.2f\n",ans),void(); for (int i=1;i<=V;++i) if (!be[i]) be[i]=++cnt; for (int i=1;i<=E;++i){ int x=e[i].x,y=e[i].y; if (be[x]!=be[y]) e[++ne].x=be[x],e[ne].y=be[y],e[ne].w=e[i].w-in[y]; } E=ne; V=cnt; root=be[root]; } } int main(){while (scanf("%d%d",&n,&m)!=EOF) init(),work(); return 0;}