UVa 908 - Re-connecting Computer Sites

　　题目大意：有n个网站，由m条线路相连，每条线路都有一定的花费，找出连接所有线路的最小花费。

　　最小生成树问题(Minimal Spanning Tree, MST)，使用Kruskal算法解决。

 #include <cstdio>

 #include <vector>

 #include <algorithm>

 using namespace std;

 typedef pair<int, int> ii;

 #define MAXN 1000100

 int p[MAXN];

 int find(int x)

 {

     return p[x] == x ? x : p[x] = find(p[x]);

 }

 int main()

 {

 #ifdef LOCAL

     freopen("in", "r", stdin);

 #endif

     int n;

     bool first = true;

     while (scanf("%d", &n) != EOF)

     {

         int u, v, w;

         int old_cost = ;

         for (int i = ; i < n-; i++)

         {

             scanf("%d%d%d", &u, &v, &w);

             old_cost += w;

         }

         int k;

         scanf("%d", &k);

         vector< pair<int, ii> > EdgeList;

         for (int i = ; i < k; i++)

         {

             scanf("%d%d%d", &u, &v, &w);

             EdgeList.push_back(make_pair(w, make_pair(u, v)));

         }

         int m;

         scanf("%d", &m);

         for (int i = ; i < m; i++)

         {

             scanf("%d%d%d", &u, &v, &w);

             EdgeList.push_back(make_pair(w, make_pair(u, v)));

         }

         sort(EdgeList.begin(), EdgeList.end());

         for (int i = ; i <= n; i++)

             p[i] = i;

         int new_cost = ;

         for (int i = ; i < EdgeList.size(); i++)

         {

             w = EdgeList[i].first;

             u = EdgeList[i].second.first;

             v = EdgeList[i].second.second;

             int pu = find(u);

             int pv = find(v);

             if (pu != pv)

             {

                 new_cost += w;

                 p[pv] = pu;

             }

         }

         if (first)  first = false;

         else  printf("\n");

         printf("%d\n%d\n", old_cost, new_cost);

     }

     return ;

 }