[NFLS 1457/4] 破坏图 题解

大意

给定一个无向图, 有边权, 任意添加一条边, 使得任意删除一条边使得图不联通的代价最大.

题解

先跑一遍 Tarjan , 建出搜索树, 显然删除不是割边的边无法使图不联通, 故将它们的边权设为 $\infty$.

然后二分答案, 将边权比答案小的边的新边权设为 $1$ , 否则设为 $0$ (包括非割边) .

若要使答案成立, 必须找到一条路径, 使得覆盖所有的 $1$ 边.

如下图, 这显然不能成立:

这个可以成立:

显然, 选择直径最优. 然后跑一遍直径, 检查是否等于 $1$ 边的个数即可.