题解：P15508 [CEOI 2012] 网络 / Network

Drink_Assam · 2026-10-20 14:01:30 · 题解

观察图的性质，由“r 可以通过一条路径到达其他任何节点 p”可知，把 SCC 缩点后是以 r 所在 SCC 为根的一棵树，而且每个 SCC 都是一个点或环。于是第一问迎刃而解，每个点答案是所在 SCC 的大小。

本题重点在第二问，首先发现连接 SCC 内的两个点没有意义。

事实上，新边只能连接祖孙关系的 SCC，这可以观察样例解释得出。证明：假如连接 u\rarr v，且 u,v 不是祖孙关系，那么 \operatorname{LCA}(u,v) 到 v 的路径就有两条，不符题意，故所有边都是后代 SCC 连向祖先 SCC。

此外，对于一个环，它在缩点后的树中的后代不能连到它的祖先，否则环内的点之间就有两条路径。

不妨把所有环的边都删掉，剩下的都连接不同 SCC，形成森林。然后现在问题变成：添加尽量少的边，使得图变成若干个环。

类似树剖，对这个森林的每棵树都剖成尽量少的连接祖孙的链，然后链尾向链头连一条新边。

代码很好写，我写得太丑极其容易影响理解，所以不放了。