因为NOI2018 day1T1的影响,补了下Kruskal重构树。其实也不算高端知识吧,但在解决"连通图中路径最大/最小值"问题上非常巧妙。
相关题目:[BZOJ3732]Network

Description

给你NN个点的无向图 ,记为: 。 图中有MM条边 ,第jj条边的长度为: .

现在有 KK 个询问 。 每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?

Input

第一行: N,M,KN, M, K。 第 2..M+12..M+1 行: 三个正整数: . 表示XXYY之间有一条长度为DD的边。 第M+2..M+K+1M+2..M+K+1行: 每行两个整数ABA B,表示询问从AA点走到BB点的所有路径中,最长的边最小值是多少?

Output

对每个询问,输出最长的边最小值是多少。

Sample Input

6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1

Sample Output

5
5
5
4
4
7
4
5

HINT

Solution

众所周知,这道题有一种解法是在最小生成树上跑 lca。和NOIp2013 火车运输一样。

另一种做法是Kruskal重构树重构完后只需要求 lca 即可。

Code

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
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define drep(i,a,b) for(re i=(a);i>=(b);--i)
inline void Chkmax(int &a,int b) {a=max(a,b);}
const int N = 30020;
int n, m, k, cnt=0;

class Edge {
public: int u, v, w;
inline bool operator < (const Edge& rhs)const{
return w < rhs.w;
}
}e[N*2];
int _=0, nxt[N*2], head[N], to[N*2], w[N*2];
inline void add(int u, int v, int W) {
nxt[++_]=head[u], head[u]=_, to[_]=v, w[_]=W;
}
#define travel(i,u) for(re i=head[u];i;i=nxt[i])

int fat[N];
inline int find(int x) { return fat[x]==x?x:fat[x]=find(fat[x]);}

int d[N], f[N][20], val[N][20];
inline int lca(int x, int y) {
int res=0;
if(d[x] < d[y]) swap(x,y);
drep(i,16,0)
if(d[f[x][i]] >= d[y])
Chkmax(res, val[x][i]), x=f[x][i];

if(x==y) return res;
drep(i,16,0)
if(f[x][i] != f[y][i]) {
Chkmax(res, val[x][i]), Chkmax(res, val[y][i]);
x = f[x][i], y = f[y][i];
}
Chkmax(res, val[x][0]), Chkmax(res, val[y][0]);
return res;
}

inline void dfs(int u) {
d[u] = d[f[u][0]]+1;
int v;
travel(i,u) {
v = to[i];
if(v==f[u][0]) continue;
f[v][0]=u, val[v][0]=w[i];
dfs(v);
}
}

inline void init(){
rep(i,1,16)
rep(x,1,n) {
f[x][i]=f[f[x][i-1]][i-1];
val[x][i]=max(val[x][i-1], val[f[x][i-1]][i-1]);
}
}

int main() {
scanf("%d%d%d", &n, &m, &k);
int u, v, W;
rep(i,1,m) {
scanf("%d%d%d", &u, &v, &W);
e[i] = (Edge) {u, v, W};
}
sort(e+1, e+m+1);
rep(i,1,n) fat[i] = i;
int p, q, now=0;
rep(i,1,m) {
p = find(e[i].u), q = find(e[i].v);
if(p!=q) {
fat[p] = q, ++now;
add(e[i].u, e[i].v, e[i].w);
add(e[i].v, e[i].u, e[i].w);
}
if(now==n-1) break;
}

dfs(1);
init();

while(k--) {
scanf("%d%d", &u, &v);
printf("%d\n", lca(u, v));
}
}

Kruskal重构树

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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
const int N = 15002;
inline int read() {
int x=0;
int f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
inline int max(int a,int b){return a>b?a:b;}

struct Edge {
int u,v,w;
inline bool operator < (const Edge &rhs)const{
return w < rhs.w;
}
}e[30002];
int n, m, k, dep[N], fa[N], val[N];

int f[N], siz[N];
int find(int x) { return !f[x]?x:f[x]=find(f[x]);}
int getdep(int x) {
if(dep[x]) return dep[x];
if(!fa[x]) return dep[x]=1;
return dep[x]=getdep(fa[x])+1;
}
inline void Kruskal() {
std::sort(e+1, e+m+1);
int num=1;
rep(i,1,m) {
int p=find(e[i].u), q=find(e[i].v);
if(p!=q) {
if(siz[p]>siz[q]) std::swap(p,q);
f[p]=q, siz[q]=max(siz[q],siz[p]+1);
fa[p]=q, val[p]=e[i].w;
if(num==n) break;
}
}
}

inline int get(int a, int b) {
int res=0;
if(dep[a]<dep[b]) std::swap(a,b);
while(dep[a]>dep[b]) res=max(res,val[a]),a=fa[a];
while(a!=b) res=max(res,max(val[a],val[b])),a=fa[a],b=fa[b];
return res;
}

int main() {
n=read(), m=read(), k=read();
rep(i,1,m) e[i] = (Edge){read(),read(),read()};
Kruskal();
rep(i,1,n) dep[i]=getdep(i);
while(k--) n=read(),m=read(),printf("%d\n", get(n,m));
return 0;
}