思路
最小瓶颈路
给定两个点u,v求两点间路径上最大边权最小，这就是最小瓶颈路问题。
解法
对于最小瓶颈路，我们通常有两种解法：
- Floyd
通过将原先dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j])改为dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j]))来计算，复杂度O(n^3) - 最小生成树
通过观察Kruskal算法的过程我们显然能够发现最小瓶颈路在最小生成树上。对于单点查询dfs就可解决问题。如果多次查询可以使用类似Floyd的处理。对于本题，我们可以离线询问，然后每次判断询问的两点是否已经相连，如果相连那么现在加入的边就是我们要求的边。代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
using namespace std;
int c, s, q;
int fa[105], ranks[105];
struct edge {
int u, v, val;
edge() {};
edge(int u, int v, int val) :u(u), v(v), val(val) {};
}E[1005];
//vector<pair<int,int>> G[105];
vector<pair<int, int>> qu;
map<pair<int, int>, int> dict;
bool cmp(edge e1, edge e2) {
return e1.val < e2.val;
}
void init_union() {
for (int i = 0;i <= c;i++) {
fa[i] = i, ranks[i] = 0;
}
}
int getfa(int x){
if (fa[x] == x)return x;
else return fa[x] = getfa(fa[x]);
}
bool same(int i, int j) {
return getfa(i) == getfa(j);
}
void unite(int i,int j) {
int a = getfa(i), b = getfa(j);
if (a == b)return;
else {
if (ranks[a] < ranks[b]) {
fa[a] = b;
}
else {
fa[b] = a;
if (ranks[a] == ranks[b])ranks[a]++;
}
}
}
int kruskal() {
init_union();
int ans = 0;
sort(E, E + s, cmp);
for (int i = 0;i < s;i++) {
if (!same(E[i].u, E[i].v)) {
ans += E[i].val;
unite(E[i].u, E[i].v);
//G[E[i].u].push_back(make_pair(E[i].v, E[i].val)), G[E[i].v].push_back(make_pair(E[i].u, E[i].val));
for (map<pair<int, int>, int>::iterator it = dict.begin();it != dict.end();it++) {
int fi = it->first.first, se = it->first.second;
if (same(fi, se) && !it->second)it->second = E[i].val;
}
}
}
return ans;
}
/*void dfs(int index) {
vis[index] = 1;
for (vector<pair<int,int>>::iterator it = G[index].begin();it != G[index].end();it++) {
int to = it->first;
if (!vis[to]) {
for (int i = 1;i <= c;i++) {
if (vis[i]) {
dp[i][to] = dp[to][i] = max(dp[i][index], it->second);
}
}
dfs(to);
}
}
}*/
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int u, v, val,cal=0;
while (cin >> c >> s >> q) {
if (c == 0 && s == 0 && q == 0)break;
int i;
for (int i = 0;i < s;i++) {
cin >> u >> v >> val;
edge e(u, v, val);
E[i] = e;
}
for (int i = 0;i < q;i++) {
cin >> u >> v;
qu.push_back(make_pair(u, v));
dict[make_pair(u, v)] = 0;
}
kruskal();
if (cal)cout << "\n";
cout << "Case #" << cal + 1 << "\n";
for (vector<pair<int, int>>::iterator it = qu.begin();it != qu.end();it++) {
int ans = dict[*it];
if (!ans)cout << "no path\n";
else cout << ans << "\n";
}
cal++;
qu.clear(),dict.clear();
}
return 0;
}