洛谷P9235 [蓝桥杯 2023 省 A] 网络稳固性

[Problem Discription]\color{blue}{\texttt{[Problem Discription]}}[Problem Discription]
给定一个 nnn 个点和 mmm 条无向边构成的图，每条边都有一个边权 ωi\omega_{i}ωi​。
一条路径的稳固性界说为这条路径上全部边的边权的最小值。
从给定节点 uuu 到 vvv 的总代价界说为从 uuu 到 vvv 的全部路径各自稳固性的最大值。假如没有路径联通 u,vu,vu,v，那么代价为 −1-1−1。
qqq 组扣问，每次扣问给定 u,vu,vu,v，求 uuu 到 vvv 的总代价。
1≤n,q≤1×105,1≤m≤3×1051 \leq n,q \leq 1 \times 10^{5},1 \leq m \leq 3 \times 10^{5}1≤n,q≤1×105,1≤m≤3×105。
[Analysis]\color{blue}{\texttt{[Analysis]}}[Analysis]
最小值最大的标题一样平常都是二分，但是这题不是。
起首是否联通可以用并查集求解，非常简朴。
可以先思量图联通的环境，不联通的环境不外也就是由几个联通的图构成。
思量一个 nnn 个点 mmm 条边的联通的图（注意这里的 n,mn,mn,m 和标题里的 n,mn,mn,m 意义不雷同）。起首先证实终极答案肯定是最大天生树里的边。
   证实仍旧是接纳反证法：假如终极答案里某一条路径不是最大天生树里的路径，那么我们思量那条不在最大天生树里的边：
  

   

• 它的边权小于最大天生树里的最小边，那么既然最大天生树就足以把图里的全部节点联通，