NOIP2024集训Day50 图论
A. [JSOI2012] 越狱老虎桥
先边双缩点，建出边双生成树。
在不额外加边的情况下，割掉树边会使子树内部断开；在加入边的情况下，若加入一条 \(1 - u\) 的边，则形成了一个 \(1 - u\) 的环，环无法通过割一条边断开；而连接树上两个节点 \((u, v)\) 的情况，把图展开后发现就是把 \(u\)，\(v\) 路径上所有点都缩进了同一个环。
此时断掉环上的边显然不合法，而不在环上的边随便断一条就能让一个点不连通。
也就是说，答案是去掉某个点对 \((u, v)\) 路径上的所有的边，剩下的边中的最小值的最大值。
设答案为 \(ans\)。那么这个问题实际等价于所有的 \(e \in E,w(e) \le ans\) 的边无法被一条路径完全覆盖。
标签：图论,环上,ans,Day50,集训,NOIP2024 From： https://www.cnblogs.com/Leirt/p/18464404