POJ.1258 Agri-Net

1.Problem
http://poj.org/problem?id=1258

2.Idea
Minimum Spanning Tree.

3.Source

 #define MAX_E 20004  
 #define MAX_V 111  
 struct edge { int u, v, cost; };  
 edge es[MAX_E];  
 int Parent[MAX_V];  
 int Size[MAX_V];  
 int V, E;  
 bool comp(const edge& e1, const edge& e2)  
 {  
      return e1.cost < e2.cost;  
 }  
 void make_set(int v) {  
      Parent[v] = v;  
      Size[v] = 1;  
 }  
 int find_set(int v) {  
      if (v == Parent[v])  
           return v;  
      return Parent[v] = find_set(Parent[v]);  
 }  
 void union_sets(int a, int b) {  
      a = find_set(a);  
      b = find_set(b);  
      if (a != b) {  
           if (Size[a] < Size[b])  
                swap(a, b);  
           Parent[b] = a;  
           Size[a] += Size[b];  
      }  
 }  
 void unit_union_find(int n)  
 {  
      for (int i = 0; i < n; i++) {  
           make_set(i);  
      }  
 }  
 bool same_set(int i, int j)  
 {  
      return find_set(i) == find_set(j);  
 }  
 int kruskal()  
 {  
      sort(es, es + E, comp);  
      unit_union_find(V);  
      ll res = 0;  
      for (int i = 0; i < E; i++) {  
           edge e = es[i];  
           if (!same_set(e.u, e.v)) {  
                union_sets(e.u, e.v);  
                res += e.cost;  
           }  
      }  
      return res;  
 }  
 int main()  
 {  
      int tmp;  
      while (cin >> V) {  
           E = 0;  
           for (int i = 0; i < V; i++)  
                for (int j = 0; j < V; j++) {  
                     cin >> tmp;  
                     if (i < j) {  
                          es[E].u = i;  
                          es[E].v = j;  
                          es[E].cost = tmp;  
                          E++;  
                     }  
                }  
           cout << kruskal() << endl;  
      }  
      return 0;  
 }