Kruskal算法
1 // 2 // main.cpp 3 // 4 // Created by Soildom on 2017/10/31. 5 // Copyright © 2017年 Soildom. All rights reserved. 6 // 7 8 #include <iostream> 9 using namespace std; 10 11 int V,E; 12 class edge { 13 public: 14 int weight,from,to; 15 bool flag=false; 16 }; 17 18 int cmp(const void *p1,const void *p2) { 19 return ((class edge*)p1)->weight-((class edge*)p2)->weight; 20 } 21 22 int union_find(int *v,int x) { 23 return (v[x]==x)?x:(v[x]=union_find(v, v[x])); 24 } 25 26 void MST(edge *e,int *v) { 27 int vnum=0,all_weight=0,x,y; 28 for (int i=0; i<E&&vnum<V-1; i++) { 29 x=union_find(v, e[i].from); 30 y=union_find(v, e[i].to); 31 if (x!=y) { 32 v[x]=y; 33 e[i].flag=true; 34 all_weight+=e[i].weight; 35 vnum++; 36 } 37 } 38 cout<<all_weight<<endl; 39 } 40 41 int main() { 42 char c1,c2; 43 cin>>V>>E; 44 edge *e=new edge[E]; 45 int *v=new int[V]; 46 for (int i=0; i<V; i++) 47 v[i]=i; 48 for (int i=0; i<E; i++) { 49 cin>>c1>>c2>>e[i].weight; 50 e[i].from=c1-'a'; 51 e[i].to=c2-'a'; 52 } 53 qsort(e, E, sizeof(edge), cmp); 54 MST(e, v); 55 delete [] e; 56 delete [] v; 57 }