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算法：
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int m,n,a,b,c,mincost[],cost[][];
bool vis[];
void Prim(){
for(int i=;i<=n;++i)
mincost[i]=cost[][i];
mincost[]=;vis[]=true;
int res=;
for(int i=;i<n;++i){//m-1个节点
int k=-;
for(int j=;j<=n;++j)//这里更新一下获得的新发现，循环到第二次时会默认地把mincost[2]当作最小值，然后与剩下的元素比较，找到最小
if(!vis[j] && (k==-||mincost[k]>mincost[j]))k=j;
if(k==-)break;
if(mincost[k]==INF)break;//如果此时的最小值还是INF，说明统计数据不足，直接退出
vis[k]=true;
res+=mincost[k];
for(int j=;j<=n;++j)
if(!vis[j])mincost[j]=min(mincost[j],cost[k][j]);
}
bool flag=false;//标记是否还有未访问
for(int i=;i<=n;++i)
if(!vis[i]){flag=true;break;}//如果还有未被访问，说明统计数据不全，输出'?'
if(flag)cout<<'?'<<endl;
else cout<<res<<endl;
}
int main()
{
while(cin>>m>>n && m){
memset(vis,false,sizeof(vis));
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
cost[i][j]=(i==j?:INF);
for(int i=;i<=m;++i){
cin>>a>>b>>c;
cost[a][b]=cost[b][a]=c;
}
Prim();
}
return ;
}
AC之Kruskal算法（并查集）：判断数据不全的依据是如果所有节点的根节点不一样，即不在同一个集合时输出'?'，否则输出最小代价即可。
#include<bits/stdc++.h>
using namespace std;
int m,n,father[],sum;
struct edge{int u,v,cost;}es[];//可能有n*(n-1)/2条边，因为这是无向有权图，此时开5000长度已经够了
bool cmp(const edge& e1,const edge& e2){//引用，减少拷贝所花时间
return e1.cost<e2.cost;
}
void init_union_find(){//将每个节点当作根节点
for(int i=;i<=n;++i)father[i]=i;
}
int find_father(int x){//递归查找根节点
if(father[x]==x)return x;
else return father[x]=find_father(father[x]);
}
void unite(int x,int y,int z){
x=find_father(x);
y=find_father(y);
if(x!=y){//如果边的两端点的根节点不相同，即分别为非连通图，则可以归并
sum+=z;//加上最小权值
father[x]=y;
}
}
int main()
{
while(cin>>m>>n && m){
for(int i=;i<=m;++i)
scanf("%d %d %d",&es[i].u,&es[i].v,&es[i].cost);
sort(es+,es+m+,cmp);//权值按从小到大排序
sum=;init_union_find();//初始化
for(int i=;i<=m;++i)
unite(es[i].u,es[i].v,es[i].cost);
bool flag=false;
for(int i=;i<=n;++i)//判断是否在同一个集合中
if(find_father()!=find_father(i)){flag=true;break;}
if(flag)cout<<'?'<<endl;
else printf("%d\n",sum);
}
return ;
}