uva 544(kruskal 变形)

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-02-05 17:03
 5  * Filename     : uva_544.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int LEN = 1010;
34 int n, m, parent[LEN], st, ed;
35 map<string, int> mp;
36 struct edge{int fr, to, val;}e[LEN*LEN];
37 
38 void init(){
39     mp.clear();
40     for(int i=0; i<LEN; i++) parent[i] = i;
41 }
42 int Find(int x){return parent[x]==x?x:parent[x] = Find(parent[x]);}
43 bool cmp(edge a, edge b){ return a.val > b.val;}
44 
45 int kruskal()
46 {
47     sort(e, e+m, cmp);
48     for(int i=0; i<m; i++){
49         int pa = Find(e[i].fr), pb = Find(e[i].to);
50         if(pa == pb) continue;
51         parent[pa] = pb;
52         if(Find(st) == Find(ed)) return e[i].val;
53     }
54 }
55 
56 int main()
57 {
58     //freopen("in.txt", "r", stdin);
59 
60     char a[101], b[101], val;
61     int ia, ib, kase = 1;
62     while(scanf("%d%d", &n, &m)!=EOF){
63         init();
64         if(!n && !m) break;
65         int cnt = 0;
66         for(int i=0; i<m; i++){
67             scanf("%s%s%d", a, b, &e[i].val);
68             if(!mp.count(a))mp[a] = ia = cnt++;
69             else ia = mp[a];
70             if(!mp.count(b))mp[b] = ib = cnt++;
71             else ib = mp[b];
72             e[i].fr = ia, e[i].to = ib;
73         }
74         scanf("%s%s", a, b);
75         st = mp[a]; ed = mp[b];
76         int ans = kruskal();
77         printf("Scenario #%d\n", kase++);
78         printf("%d tons\n\n", ans);
79     }
80     return 0;
81 }