SS241030C. 桥梁(bridge)

题意

本人小时候也分不清 fridge 和 bridge

给你 \(n\) 个点，\(m\) 条边的图，边带权。有 \(q\) 个要求。每个要求给出 \(a_i,b_i\)，要求至少选中第 \(a_i\) 或 \(b_i\) 条边。问最小代价选边使得图连通。

solution

注意到 \(q\le 16\)，可以直接枚举每个要求必须选择 \(a\) 还是 \(b\)，有 \(2^q\) 种选法。

注：以下的 最小生成树 其实建出来不一定是树，因为有可能必选的边会成环。

暴力是跑 \(2^q\) 次最小生成树。时间复杂度 \(O(n2^q)\)，可以得到 \(36pts\)。

注意到每次跑生成树，强制要选的边变化不多，因此最终选择出来的边有很大一部分是重复的。

假设强制选上所有的 \(a_i,b_i\)，跑最小生成树，选上的那些没有被强制选择的边，在所有要求方式中，这些边一定会被选中，把它们叫做关键边。考虑证明。取消选择一些 \(a,b\)，可能会出现多个连通块，你可能选择其他边替代取消的 \(a,b\)，但是这些新边是无法代替关键边的作用的，因为选上所有 \(a,b\) 的时候，关键边的两端处在不同的连通块，所以连上新边，关键边的两端仍然处在不同的连通块。

只连所有的关键边，会形成 \(O(q)\) 个连通块。

把每个连通块缩成一个点，处理出它们间的 \(O(q^2)\) 条边。

枚举要求状态，然后先选择必选的边，然后在 \(O(q)\) 个点，\(O(q^2)\) 条边的图上做最小生成树即可。

错误结论 1：没有要求地跑一遍最小生成树，没有跑到的边一定不会被选中。结论错误。

错误结论 2：std 的题解说，强制不选择所有的 \(a_i,b_i\)，跑最小生成树，没有被选中的边一定在所有状态都不会被选中。这个结论是正确的，但是？

时间复杂度 \(O(2^q q^2)\)。

代码比较丑，不放了。