poj 1258 Agri-Net

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 #define maxn 200
 6 int a[maxn][maxn];
 7 int par[maxn];
 8 int n,len;
 9 int num;
10 struct node
11 {
12     int x;
13     int y;
14     int w;
15 };
16 node e[maxn * maxn / 2];
17 int cmp(const node& a,const node &b)
18 {
19     return a.w < b.w;
20 }
21 int Find(int k)
22 {
23     if(par[k] == k)   return k;
24     par[k] = Find(par[k]);
25     return par[k];
26 }
27 void Merge(int x,int y)
28 {
29     int a = Find(x);
30     int b = Find(y);
31     if(a != b)
32     {
33         par[a] = b;
34     }
35 }
36 
37 void kruskal()
38 {
39 
40     while(cin>>n)
41     {
42         for(int i = 0; i <= n+5; i++)
43             par[i] = i;
44         num = 0;
45         len = 0;
46         for(int i = 1; i <= n; i++)
47             for(int j = 1; j <= n; j++)
48                 cin>>a[i][j];
49 
50         for(int i = 1; i <= n; i++)
51             for(int j = i + 1; j <= n; j++)
52             {
53                 e[num].x = i;
54                 e[num].y = j;
55                 e[num++].w = a[i][j];
56             }
57         sort(e,e+num,cmp);
58         for(int i = 0; i < num; i++)
59         {
60             if(Find(e[i].x) != Find(e[i].y))
61             {
62                 Merge(e[i].x,e[i].y);
63                 len += e[i].w;
64             }
65         }
66         cout<<len<<endl;
67     }
68 
69 }
70 int main()
71 {
72     freopen("input.txt","r",stdin);
73     kruskal();
74 
75     return 0;
76 }