题目链接 https://vjudge.net/problem/UVA-544
【题意】
给定一张n个点m条边的无向图，并给定起点和终点，求起点到终点的一条路径，使得这条路径上边的最小权值尽量大。
【思路】
这个问题刚好和最小瓶颈路反过来了，最小瓶颈路是要求路径上的最大权值尽量小，所以我们可以按照权值对边集降序排序，然后用kruscal构造最大生成树，那么构造的过程中第一次将起点和终点连通的那条边就是答案。
#include<bits/stdc++.h>
using namespace std;const int maxn = 220;
const int maxm = 20050;struct Edge {int from, to, dist;Edge(int f = 0, int t = 0, int d = 0) :from(f), to(t), dist(d) {}bool operator<(const Edge& e) const {return dist > e.dist;//权值大的优先}
};int n, m, cnt;
int st, en;
int par[maxn];
map<string, int> mp;
vector<Edge> edges;int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }void kruscal() {for (int i = 0; i <= n; ++i) par[i] = i;for (int i = 0; i < m; ++i) {int x = find(edges[i].from);int y = find(edges[i].to);if (x != y) {par[x] = y;if (find(st) == find(en)) {printf("%d tons\n\n", edges[i].dist);return;}}}
}int main() {int kase = 0;while (scanf("%d%d", &n, &m) == 2) {if (0 == n && 0 == m) break;cnt = 0;mp.clear();edges.clear();char s1[50], s2[50];for (int i = 0; i < m; ++i) {int d;scanf("%s%s%d", s1, s2, &d);if (0 == mp[string(s1)]) mp[string(s1)] = ++cnt;if (0 == mp[string(s2)]) mp[string(s2)] = ++cnt;int u = mp[string(s1)], v = mp[string(s2)];edges.push_back(Edge(u, v, d));}scanf("%s%s", s1, s2);st = mp[string(s1)], en = mp[string(s2)];sort(edges.begin(), edges.end());printf("Scenario #%d\n", ++kase);kruscal();}return 0;
}