本文共 2049 字，大约阅读时间需要 6 分钟。
POJ2377
题意：求最大生成树
分析：把边权值变成负值，最后取绝对值，注意最后的判断，如果生成树的边的数目小于(顶点数－1)则表示不能构成生成树
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std;14 const int maxn=20020;15 int par[maxn],rankl[maxn];16 17 void init(int n)18 {19 for(int i=0;i<=n;i++)20 {21 par[i]=i;22 rankl[i]=0;23 }24 }25 int findl(int x)26 {27 if(par[x]==x)28 return x;29 else30 return par[x]=findl(par[x]);31 }32 void unite(int x,int y)33 {34 x=findl(x);35 y=findl(y);36 if(x==y) return;37 if(rankl[x] >n>>m)75 {76 for(int i=0;i
AOJ2224
题意：给定一个图，并给出每条边的一些信息，问要让这个图构成树，去掉的最小长度是多少
分析：因为求的是去掉的最小长度，所以剩下的必然是最大的，这就是一个最大生成树问题，注意一下输入问题，开始给定的是点的坐标，后面给定的是哪些点是联通的
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std; 14 const int maxn=10100; 15 const int maxm=10000*10000/2; 16 int par[maxn],rankl[maxn]; 17 18 //并查集 19 void init(int n) 20 { 21 for(int i=0;i<=n;i++) 22 { 23 par[i]=i; 24 rankl[i]=0; 25 } 26 } 27 int findl(int x) 28 { 29 if(par[x]==x) 30 return x; 31 else 32 return par[x]=findl(par[x]); 33 } 34 void unite(int x,int y) 35 { 36 x=findl(x); 37 y=findl(y); 38 if(x==y) return; 39 if(rankl[x] >n>>m) 90 { 91 memset(a,0,sizeof(a)); 92 memset(b,9,sizeof(b)); 93 for(int i=1;i<=n;i++) //输入点的坐标 94 { 95 scanf("%lf%lf",&a[i],&b[i]); 96 } 97 double hh=0.0; 98 for(int i=1;i<=m;i++) //输入有边的点 99 {100 scanf("%d%d",&s[i].x,&s[i].y);101 int x=s[i].x,y=s[i].y;102 es[i].u=x,es[i].v=y;103 es[i].cost=-distance(a[x],b[x],a[y],b[y]);104 hh+=-es[i].cost;105 }106 double tt=0-kruskal();107 printf("%.3lf\n",hh-tt);108 }109 return 0;110 }
转载于:https://www.cnblogs.com/wolf940509/p/5751684.html
