uva 1208 - Oreon

  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 <map>
 13  #include <vector>
 14  using namespace std;
 15  
 16  const int maxn = 30;
 17  
 18  class Edge
 19  {
 20  public:
 21      int a,b,t;
 22  
 23      Edge(int aa, int bb, int tt): a(min(aa,bb)), b(max(aa,bb)), t(tt)
 24      {
 25      }
 26  
 27  
 28  };
 29  
 30  map<int,char> city;
 31  vector<Edge> Elist;
 32  int fa[maxn];
 33  int n;
 34  
 35  void readfile();
 36  bool cmp(const Edge& R1, const Edge& R2);
 37  bool ok(const Edge E);
 38  
 39  int main()
 40  {
 41      int ntest;
 42      cin >> ntest;
 43      for (int test=1; test<=ntest; test++)
 44      {
 45          int cnt = 0;
 46          readfile();
 47          for (int i=1; i<=n; i++) fa[i] = i;
 48          sort(Elist.begin(), Elist.end(), cmp);
 49          printf("Case %d:\n",test);
 50          for (vector<Edge>::size_type i=0; i<Elist.size(); i++)
 51              if (ok(Elist[i]))
 52              {
 53                  cout << city[Elist[i].a] << "-" << city[Elist[i].b] << " " << Elist[i].t << endl;
 54                  cnt++;
 55                  if (cnt==n-1) break;
 56              }
 57          Elist.clear();
 58          city.clear();
 59      }
 60      return 0;
 61  }
 62  
 63  void readfile()
 64  {
 65      string num;
 66      int value;
 67      cin >> n;
 68      for (int i=1; i<=n; i++) city[i] = char(64+i);
 69  
 70      for (int i=1; i<=n; i++)
 71          for (int j=1; j<=n; j++)
 72          {
 73              cin >> num;
 74              value = 0;
 75              unsigned int k = 0;
 76              while (k<num.length() && num[k]>='0' && num[k]<='9')
 77              {
 78                  value = value*10 + int(num[k])-48;
 79                  k++;
 80              }
 81              if (value>0) Elist.push_back(Edge(i,j,value));
 82          }
 83  }
 84  
 85  bool ok(const Edge E)
 86  {
 87      int a = E.a,
 88          b = E.b;
 89      while (a!=fa[a]) a = fa[a];
 90      while (b!=fa[b]) b = fa[b];
 91      if (a==b) return(false);
 92      else
 93      {
 94          a<b? fa[b]=a : fa[a]=b;
 95          return(true);
 96      }
 97  }
 98  
 99  bool cmp(const Edge& R1, const Edge& R2)
100  {
101      if (R1.t<R2.t) return(true);
102      else if (R1.t==R2.t && R1.a<R2.a) return(true);
103      else if (R1.t==R2.t && R1.a==R2.a && R1.b<R2.b) return(true);
104      return(false);
105  }