uva 908 - Re-connecting Computer Sites

 1  /*
 2  Problem link
 3  Type: Graph
 4  Algorithm: MST
 5  */
 6  #include <iostream>
 7  #include <cstdio>
 8  #include <cstdlib>
 9  #include <cstring>
10  #include <cmath>
11  #include <algorithm>
12  #include <vector>
13  using namespace std;
14  
15  const int maxn = 1000010;
16  
17  class Edge {
18  public:
19      int a;
20      int b;
21      int t;
22  
23      Edge(int aa, int bb, int tt) : a(aa), b(bb), t(tt) {}
24  };
25  
26  vector<Edge> Elist;
27  int n,m,w1,k,w2;
28  int fa[maxn];
29  
30  bool cmp(const Edge& R1, const Edge& R2) { return (R1.t<R2.t); }
31  bool ok(Edge R);
32  
33  int main()
34  {
35      int ntest = 0;
36  
37      while (!cin.eof())
38      {
39          cin >> n;
40          if (cin.eof()) break;
41          Elist.clear();
42          ntest++;
43          if (ntest>1) cout << endl;
44          int x, y, value, cnt = 0;
45          w1 = 0;
46          w2 = 0;
47  
48          for (int i=1; i<=n; i++) fa[i] = i;
49          for (int i=1; i<=n-1; i++)
50          {
51              cin >> x >> y >> value;
52              w1+=value;
53          }
54          cin >> k;
55          for (int i=1; i<=k; i++)
56          {
57              cin >> x >> y >> value;
58              Elist.push_back(Edge(x,y,value));
59          }
60          cin >> m;
61          for (int i=1; i<=m; i++)
62          {
63              cin >> x >> y >> value;
64              Elist.push_back(Edge(x,y,value));
65          }
66          sort(Elist.begin(), Elist.end(), cmp);
67  
68          for (vector<Edge>::size_type i=0; i<Elist.size(); i++)
69              if (ok(Elist[i]))
70              {
71                  w2+=Elist[i].t;
72                  cnt++;
73                  if (cnt==n-1) break;
74              }
75          cout << w1 << endl << w2 << endl;
76      }
77      return 0;
78  }
79  
80  bool ok(Edge R){
81      int a = R.a, b = R.b;
82      while (a!=fa[a]) a = fa[a];
83      while (b!=fa[b]) b = fa[b];
84      if (a==b) return(false);
85      else
86      {
87          a<b? fa[b] = a : fa[a] = b;
88          return(true);
89      }
90  }