题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1233
#include#include #include #include #define MAXN 105#define MAXM 10000using namespace std;/**************************************************************************************************** 题意：给出城市中任意两个村庄的编号和距离，修一条公路使所有村庄联通，求最小的公路总长度 思路： 1，最小生成树算法，用 Kruskal算法 2，利用并查集维护每个联通集合 3，好好理解算法 PS:模板在邝斌的基础上做了修改，更加便于理解****************************************************************************************************/int F[MAXN]; //并查集维护联通集合struct Node{ int x,y,v;}node[MAXM];bool cmp(Node x,Node y){ return x.v < y.v;}int Find(int x){ //找到每个点的父亲结点。（因为树的形状不重要，因此遍历之后将遍历过的结点改为树根的子结点） if(F[x] == -1) return x; else return F[x] = Find(F[x]);}int Kruskal(int n){ int tol = (n*(n-1))/2; //由点数确定边数 memset(F,-1,sizeof(F)); sort(node+1,node+tol+1,cmp); //将边排序后从小到大加入集合 int cnt = 0,ans = 0; for(int i = 1;i <= tol;i ++){ int t1 = Find(node[i].x),t2 = Find(node[i].y); if(t1 != t2){ ans += node[i].v; F[t1] = t2; cnt++; } if(cnt == n-1) break; } if(cnt < n-1) return -1; else return ans;}int main(){ int n; while(cin>>n,n != 0){ int x,y,v; for(int i = 1;i <= (n*(n-1))/2;i ++) scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].v); int ans = Kruskal(n); cout< <