# POJ_1251（kruskal算法）

POJ_1251，求最小生成树，这里采用基于并查集路径压缩的kruskal算法。

prim算法复杂度：v^2：每个(v)找直接相连边(v)
kruskal算法复杂度：eloge：将边按权值排序

``````#include
#include
#include
using namespace std;
struct way{
int v1ofway,v2ofway,cost;
};
way ways[80];
int father[30];

bool comp(way way1,way way2){
return way1.cost<way2.cost;
}

int findfather(int v){
int temp=v;
while(v!=father[v]) 	v = father[v];	//查找
//优化压缩路径
while(temp!=father[temp]){
int t_temp = temp;
temp = father[temp];
father[t_temp] = v;
}
return v;
}

int kruskal(int villagenum,int waynum){
sort(ways,ways+waynum,comp);	//结构体数组排序写法
for(int i=0;i<villagenum;i++){
father[i]=i;
}
int cost=0;
for(int i=0,j=0;j<villagenum-1;i++){
int v1=ways[i].v1ofway;		int v2=ways[i].v2ofway;
v1 = findfather(v1);		v2 = findfather(v2);
if(v1!=v2){
father[v2] = v1;
j++;
cost+=ways[i].cost;
}
}
return cost;
}

int main(){
int villagenum;
while(cin>>villagenum){
if(villagenum==0)	break;
for(int i=0;i<80;i++){
ways[i].v1ofway=0;	ways[i].v2ofway=0;	ways[i].cost=0;
}
for(int i=0;i<30;i++){
father[i]=0;
}
int waynum=0;
for(int i=0;i<villagenum-1;i++){
char village1;	cin>>village1;
int v1ways;		cin>>v1ways;
for(int j=0;j<v1ways;j++){
char village2;	cin>>village2;
ways[waynum].v1ofway=village1-'A';
ways[waynum].v2ofway=village2-'A';
cin>>ways[waynum].cost;
waynum++;
}
}
cout<<kruskal(villagenum,waynum)<<endl;
}
return 0;
}
``````