uva 11710 - Expensive subway

/*

Problem link

Type: Graph

Algorithm: Minimum spanning tree

*/

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