Problem Description
省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100
)；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
Output
对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
Sample Input
3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100
Sample Output
3
?
这题我是用kruskal算法写的，该算法的实质是并查集，如果不懂的，把并查集好好看一看。
#include<stdio.h> #include<algorithm> using namespace std; typedef struct{ int st,ed; int len; }enodge; int cmp(enodge a,enodge b) { return a.len<b.len; } enodge edge[10010];//记录信息 int father[110],rank[110];//father[x]保存x的父节点，rank[x]记录x的秩 int find(int x)//寻找父节点 { if(x!=father[x]) father[x]=find(father[x]);//回溯时路径压缩 return father[x]; } void kruskal(int n,int m) { int i,ans,sum,x,y; sum=0;ans=0; sort(edge+1,edge+1+n,cmp); for(i=1;i<=n;i++)//这里实质是并查集中的合并操作 { x=find(edge[i].st); y=find(edge[i].ed); if(x!=y) { sum+=edge[i].len; if(rank[x]>rank[y]) father[y]=x; else if(rank[y]<rank[x]) father[x]=y; else { rank[x]++; father[y]=x; } ans++; if(ans==m-1) break;//如果选择了m-1条边，则跳出循环 } } if(ans==m-1) printf("%d\n",sum); else printf("?\n"); } int main() { int n,m,i; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0) break; for(i=1;i<=m;i++) { father[i]=i; rank[i]=0; } for(i=1;i<=n;i++) scanf("%d%d%d",&edge[i].st,&edge[i].ed,&edge[i].len); kruskal(n,m); } return 0; }