POJ.3723 Conscription

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

2.Idea
Calculating the minimum cost by Kruskal algorithm.

3.Source

 #define MAX_R 50004  
 #define MAX_V 20003  
 struct edge { int u, v, cost; };  
 int Parent[MAX_V];  
 int Size[MAX_V];  
 int N, M, R, V, E;  
 edge es[MAX_R];  
 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);  
      int 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 t;  
      cin >> t;  
      while (t--) {  
           cin >> N >> M >> R;  
           V = N + M;  
           E = R;  
           for (int i = 0; i < R; i++) {  
                scanf("%d%d%d", &es[i].u, &es[i].v, &es[i].cost);  
                es[i].v += N;  
                es[i].cost *= -1;  
           }  
           cout << 10000 * V + kruskal() << endl;  
      }  
      return 0;  
 }