uva 11733 - Airports

 1 /*
 2  Problem link
 3  Type: Graph
 4  Algorithm:
 5      Kruskal, stop when the number of edge selected is equal to n-1 or the price of the edge
 6      equal to the cost to build an airport.
 7  */
 8  #include <iostream>
 9  #include <cstdio>
10  #include <cstring>
11  #include <cmath>
12  #include <vector>
13  #include <algorithm>
14  
15  using namespace std;
16  const int maxn = 10010;
17  
18  class Edge
19  {
20  public:
21      int a,b,t;
22  
23      Edge() {}
24      Edge(int aa, int bb, int tt): a(aa), b(bb), t(tt) {}
25      Edge(const Edge& p) { a =p.a; b=p.b; t = p.t; }
26  
27      bool operator<(const Edge& p) { return this->a<p.a; }
28      bool operator>(const Edge& p) { return this->a>p.a; }
29  };
30  
31  bool cmp2(const Edge& e1, const Edge& e2)
32  {
33      return e1.t<e2.t;
34  }
35  
36  vector<Edge> eList;
37  int fa[maxn],start[maxn],endd[maxn];
38  int n,m,k;
39  
40  void ReadFile();
41  int KrusKal(int &tplt);
42  bool Ok(Edge p);
43  
44  int main()
45  {
46      int nTest;
47      cin >> nTest;
48      for (int test=1; test<=nTest; test++)
49      {
50          eList.clear();
51          int eps = 0, result;
52          ReadFile();
53          for (int i=0; i<=n; i++) fa[i] = i;
54          result = KrusKal(eps);
55          printf("Case #%d: %d %d\n",test,result,eps);
56      }
57      return 0;
58  }
59  
60  void ReadFile()
61  {
62      cin >> n >> m >> k;
63      for (int i=1; i<=m; i++)
64      {
65          int u,v,t;
66          cin >> u >> v >> t;
67          eList.push_back(Edge(u,v,t));
68      }
69  }
70  
71  int KrusKal(int &tplt)
72  {
73      int result = 0, cnt = 0;
74      sort(eList.begin(),eList.end(),cmp2);
75      for (int i=1; i<=n; i++) fa[i] = i;
76      for (unsigned int i=0; i<eList.size(); i++)
77          if (Ok(eList[i]))
78          {
79              if (eList[i].t>=k) break;
80              cnt++;
81              result += eList[i].t;
82              if (cnt==n-1) break;
83          }
84      tplt = n-cnt;
85      return (result+(n-cnt)*k);
86  }
87  
88  bool Ok(Edge p)
89  {
90      int a = p.a, b = p.b;
91      while (a!=fa[a]) a = fa[a];
92      while (b!=fa[b]) b = fa[b];
93      if (a==b) return(false);
94      if (a<b) fa[b] = a;
95      else fa[a] = b;
96      return true;
97  }