链接
[http://acm.hdu.edu.cn/showproblem.php?pid=1863]
题意
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
?
分析
Kruskal求最小生成树
代码
#include<iostream>
#include<algorithm>
using namespace std;
int par[1000];//祖先
int r[1000];//祖先的等级
typedef struct{//a到b以及距离
int a,b,price;
}node;
node a[1000];
bool cmp(node &x,node &y){
return x.price<y.price;
}
void init(int n){
for(int i=1;i<=n;i++){
par[i]=i; r[i]=1;//刚开始祖先是自己，祖先等级是1
}
}
int find(int x){
if(x==par[x]) return par[x];//如果祖先是自己返回
else{
par[x]=find(par[x]); return par[x];//祖先是它祖先的祖先
}
}
void merge(int u,int v){//合并二者的祖先
int f1=find(u);
int f2=find(v);
if(r[f1]<r[f2]){//如果u的祖先等价低于v的祖先就等级优先
par[f1]=f2;
}
else{//否则相反
par[f2]=f1;
if(r[f1]==r[f2]) r[f1]++; //如果祖先等级相同优先前者等级加1
}
}
int Kruskal(int n,int m){
int edge=0,sum=0;
sort(a+1,a+n+1,cmp);//对所有边按距离从小到大排序
for(int i=1;i<=n&&edge!=m-1;i++){//当求到m-1条边说明已经联通
if(find(a[i].a)!=find(a[i].b)){//对每条边找祖先如果不同说明没联通可以合并祖先
merge(a[i].a,a[i].b);
sum+=a[i].price;//总路程加这条边的距离
edge++;//统计边数
}
}
if(edge<m-1) sum=-1;//如果边少于m-1说明是无法联通的
return sum;
}
int main()
{
int n,m,ans;
//freopen("in.txt","r",stdin);
while(cin>>n>>m&&n){
init(m);
for(int i=1;i<=n;i++)
{
cin>>a[i].a>>a[i].b>>a[i].price;
}
ans=Kruskal(n,m);
if(ans==-1) cout<<"?\n";
else cout<<ans<<endl;
}
return 0;
}