题意:在一张无向带权图中,求a-b的一条路经满足这条路径上的最小的边最大。
思路:仔细一看就能发现这不是最小瓶颈路的变形嘛,最小瓶颈路是让你求最大的边最小,这道题的意思就是反了一下,而且还是单组询问的。所以我们用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 }