Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从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
?
解题思路：全省畅通也就是求最小生成树，如果给出的数据不全，得到的将是INF，此时输出'?'，否则输出对应的最小代价。
AC代码之Prim算法：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 int m,n,a,b,c,mincost[105],cost[105][105]; 5 bool vis[105]; 6 void Prim(){ 7 for(int i=1;i<=n;++i) 8 mincost[i]=cost[1][i]; 9 mincost[1]=0;vis[1]=true; 10 int res=0; 11 for(int i=1;i<n;++i){//m-1个节点 12 int k=-1; 13 for(int j=1;j<=n;++j)//这里更新一下获得的新发现，循环到第二次时会默认地把mincost[2]当作最小值，然后与剩下的元素比较，找到最小 14 if(!vis[j] && (k==-1||mincost[k]>mincost[j]))k=j; 15 if(k==-1)break; 16 if(mincost[k]==INF)break;//如果此时的最小值还是INF，说明统计数据不足，直接退出 17 vis[k]=true; 18 res+=mincost[k]; 19 for(int j=1;j<=n;++j) 20 if(!vis[j])mincost[j]=min(mincost[j],cost[k][j]); 21 } 22 bool flag=false;//标记是否还有未访问 23 for(int i=1;i<=n;++i) 24 if(!vis[i]){flag=true;break;}//如果还有未被访问，说明统计数据不全，输出'?' 25 if(flag)cout<<'?'<<endl; 26 else cout<<res<<endl; 27 } 28 int main() 29 { 30 while(cin>>m>>n && m){ 31 memset(vis,false,sizeof(vis)); 32 for(int i=1;i<=n;++i) 33 for(int j=1;j<=n;++j) 34 cost[i][j]=(i==j?0:INF); 35 for(int i=1;i<=m;++i){ 36 cin>>a>>b>>c; 37 cost[a][b]=cost[b][a]=c; 38 } 39 Prim(); 40 } 41 return 0; 42 }
AC之Kruskal算法（并查集）：判断数据不全的依据是如果所有节点的根节点不一样，即不在同一个集合时输出'?'，否则输出最小代价即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int m,n,father[105],sum; 4 struct edge{int u,v,cost;}es[5000];//可能有n*(n-1)/2条边，因为这是无向有权图，此时开5000长度已经够了 5 bool cmp(const edge& e1,const edge& e2){//引用，减少拷贝所花时间 6 return e1.cost<e2.cost; 7 } 8 void init_union_find(){//将每个节点当作根节点 9 for(int i=1;i<=n;++i)father[i]=i; 10 } 11 int find_father(int x){//递归查找根节点 12 if(father[x]==x)return x; 13 else return father[x]=find_father(father[x]); 14 } 15 void unite(int x,int y,int z){ 16 x=find_father(x); 17 y=find_father(y); 18 if(x!=y){//如果边的两端点的根节点不相同，即分别为非连通图，则可以归并 19 sum+=z;//加上最小权值 20 father[x]=y; 21 } 22 } 23 int main() 24 { 25 while(cin>>m>>n && m){ 26 for(int i=1;i<=m;++i) 27 scanf("%d %d %d",&es[i].u,&es[i].v,&es[i].cost); 28 sort(es+1,es+m+1,cmp);//权值按从小到大排序 29 sum=0;init_union_find();//初始化 30 for(int i=1;i<=m;++i) 31 unite(es[i].u,es[i].v,es[i].cost); 32 bool flag=false; 33 for(int i=2;i<=n;++i)//判断是否在同一个集合中 34 if(find_father(1)!=find_father(i)){flag=true;break;} 35 if(flag)cout<<'?'<<endl; 36 else printf("%d ",sum); 37 } 38 return 0; 39 }