题目:
1233 | 还是畅通工程 |
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 #define M 101 8 typedef struct{ 9 int x,y; 10 int len; 11 }EDGE; 12 13 EDGE edge[M*M]; 14 int Map[M][M]; 15 int n,m; 16 int set[M]; 17 18 void ReadMap(); 19 void InitSet(); 20 int cmp(const EDGE &a,const EDGE &b); 21 int FindSet(int a); 22 void MergeSet(int a,int b); 23 void main() 24 { 25 int c,s,f,t; 26 while (scanf("%d",&n),n) 27 { 28 m = (n*(n-1))>>1; 29 ReadMap(); 30 InitSet(); 31 c = 0;//choosed node 32 s = 0;//sum length 33 sort(edge,edge+m,cmp);//sort the edges 34 for (int i=0;i<m && c!=n;i++) 35 { 36 f = FindSet(edge[i].x); 37 t = FindSet(edge[i].y); 38 if (f!=t) 39 { 40 MergeSet(f,t); 41 c++; 42 s += edge[i].len; 43 } 44 } 45 cout<<s<<endl; 46 47 } 48 } 49 void ReadMap() 50 { 51 for (int i=0;i<m;i++) 52 cin>>edge[i].x>>edge[i].y>>edge[i].len; 53 } 54 void InitSet() 55 { 56 for (int i=1;i<=n;i++) 57 set[i] = i; 58 } 59 int cmp(const EDGE &a,const EDGE &b) 60 { 61 return a.len<b.len; 62 } 63 int FindSet(int a) 64 { 65 return set[a]; 66 } 67 void MergeSet(int a,int b) 68 { 69 for (int i=1;i<=n;i++) 70 { 71 if (set[i] == a) 72 { 73 set[i] = b; 74 } 75 } 76 }
本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/archive/2012/10/09/2716903.html,如需转载请自行联系原作者