「题解」BZOJ 3732「Network」

分析

这题也是裸的最小瓶颈路,kruskal重构树和LCA解决

代码

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
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
const int MAXN = 15000 * 4 + 6;
int fa[MAXN],val[MAXN],cnt,dep[MAXN],t,f[MAXN][20];
struct Edge{
int v,d;
Edge(){}
Edge(int v,int d){
this -> v = v;
this -> d = d;
}
};
struct Edge2{
int u,v,d;
Edge2(){}
Edge2(int u,int v,int d){
this -> u = u;
this -> v = v;
this -> d = d;
}
bool operator < (const Edge2 &rhs) const{
return d < rhs.d;
}
};Edge2 E[MAXN];
std::vector<Edge> G[MAXN];
std::queue<int> Q;
inline void addEdge(int u,int v){G[u].push_back(Edge(v,666));}
int get(int x){return x == fa[x] ? x : fa[x] = get(fa[x]);}
void bfs(int s){
int x,y;
dep[s] = 1;
Q.push(s);
while(Q.size()){
x = Q.front();Q.pop();
for(int i = 0;i < G[x].size();i++){
y = G[x][i].v;
if(dep[y]) continue;
dep[y] = dep[x] + 1;
f[y][0] = x;
for(int j = 1;j <= t;j++) f[y][j] = f[f[y][j - 1]][j - 1];
Q.push(y);
}
}
}
int lca(int x,int y){
if(dep[x] > dep[y]) std::swap(x,y);
for(int i = t;i >= 0;i--) if(dep[f[y][i]] >= dep[x]) y = f[y][i];
if(x == y) return x;
for(int i = t;i >= 0;i--) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
return f[x][0];
}
void kruskal(int n,int m){
int u,v;cnt = n;
std::sort(E + 1,E + 1 + m);
for(int i = 1;i <= n;i++) fa[i] = i;
for(int i = 1;i <= m;i++){
u = get(E[i].u),v = get(E[i].v);
if(u != v){
cnt++;
val[cnt] = E[i].d;
fa[cnt] = fa[u] = fa[v] = cnt;
addEdge(u,cnt);addEdge(cnt,u);
addEdge(v,cnt);addEdge(cnt,v);
}
}
t = (int)log(cnt) / log(2) + 1;
}
int main(){
int n,m,u,v,k;scanf("%d %d %d",&n,&m,&k);
for(int i = 1;i <= m;i++) scanf("%d %d %d",&E[i].u,&E[i].v,&E[i].d);
kruskal(n,m);bfs(cnt);
while(k--){
scanf("%d %d",&u,&v);
printf("%d\n",val[lca(u,v)]);
}

return 0;
}
分享到