题解：P11852 [TOIP 2023] 公路

MaxFwl · 2025-03-17 16:08:05 · 题解

先考虑如何判是否有解，只需要提前处理出每一个边双连通分量即可，复杂度 O(m)。

于是我们只需要求出每一个在同一个边双连通分量的点对的对应答案，可以把一张图分成若干个边双连通分量，在这些分量中求解答案。

考虑到边双连通分量的性质不够优秀，综合题意，我们考虑建出它的 MST。

对于不在 MST 上的边，我们按边权从小到大加入，每次找到新的满足要求的点对，我们发现所有新点对一定在该边的两端在 MST 上的路径上经过的边双连通分量中，并且这些边双连通分量会形成一个新的边双连通分量。

我们使用并查集维护每一个形成的边双连通分量，用 vector 存下每一个双连通分量中包含的点集，合并时暴力合并 vector 即可。

我们来分析复杂度，建 MST 的复杂度是 O(m \log{m}) 的，向上合并 vector 是 O(n^2) 的，因为每个点最多向上合并 O(n) 次，求解答案的复杂度也是 O(n^2) 的，因为每个有解的点对只需要一次赋值操作。

总复杂度 O(m \log{m} + n^2)，作者在实现时使用了启发式合并，不过只有常数上的影响，code。