Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom7月前

12/6
20:49
kruskal LCA

[bzoj 3732] Network

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

给你N个点的无向图 (1 <= N <= 15,000),记为:1…N。
图中有M条边 (1 <= M <= 30,000) ,第j条边的长度为: d_j ( 1 < = d_j < = 1,000,000,000).

现在有 K个询问 (1 < = K < = 15,000)。
每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行: N, M, K。
第2..M+1行: 三个正整数:X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。
第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?

♦♦♦♦♦♦   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   ♦♦♦♦♦♦

1 <= N <= 15,000
1 <= M <= 30,000
1 <= d_j <= 1,000,000,000
1 <= K <= 15,000

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

先求出最小生成树,也就是一棵最小瓶颈生成树,对于一个询问,就是求这2个点在这棵树上路径的最大值,倍增lca搞一下就好了

 

[bzoj 3732] Network