每日算法--最小生成树--克鲁斯卡尔（Kruskal）算法
畅通工程
题面;
解题思路：求最小生成树，可以运用克鲁斯卡尔算法和Prime算法。
#include<iostream>
#include<algorithm>
#include<algorithm>
#define ll long long
using namespace std;
ll N,M;
const int max_n=111;
struct node{
ll from,to;
ll cost;/*花费多少*/
}E[max_n*max_n];
//实现并查集算法
ll father[max_n];
void init(){/*初始化*/
for(int i=1;i<=max_n;i++){
father[i]=i;
}
}
ll Find(ll x){
if(x==father[x]){
return x;
}else{
return father[x]=Find(father[x]);
}
}
void merge(int x,int y){
int p=Find(x);
int q=Find(y);
if(p!=q){
father[p]=q;
}
}
bool Same(int x,int y){
return Find(x)==Find(y);
}
bool cmp(node a,node b){
return a.cost<b.cost;
}
ll Kluskal(){
sort(E+1,E+1+N,cmp);
ll res=0;
for(int i=1;i<=N;i++){
if(Same(E[i].from,E[i].to)){
continue;
}else{
merge(E[i].from,E[i].to);
res+=E[i].cost;
}
}
return res;
}
int main(){
while(cin>>N>>M){/*道路条数 村庄数目*/
if(N==0){
break;
}
init();
for(int i=1;i<=N;i++){
cin>>E[i].from>>E[i].to>>E[i].cost;
}
ll res=Kluskal();
for(int i=1;i<=M;i++){
if(!Same(i,1)){
res=-1;
}
}
if(res==-1){
printf("?\n");
}else{
printf("%lld\n",res);
}
}
return 0;
} 
