CF906C Party

洛谷：CF906C Party

Codeforces：CF906C Party

Problem

有 \(n\) 个人，给定他们的初始认识情况，每次操作可以选择一个人，让他当前认识的所有的人都相互认识。

问至少操作几次使得所有人都相互认识，并给出任意合法且次数最少的操作方案。保证操作方案存在。

Solution

\(n \le 22\)，考虑状压。

可以想到这个过程是一堆孤立的点集不断融合，最后形成一个完全图。

然而同时对多个连通块进行合并是不好设计 DP 状态和转移的。于是我们换一个思路：考察某个特定的 连通块点集至少需要几次才能出现，我们用 \(f_S\) 表示到达完全图点集 \(S\) 所需的最小操作次数。

然而本质问题还是没有解决：多个连通块的合并或者说扩张是独立进行的，这并不好 DP。

对于连续两个操作的点 \(x, y\)，它们的先后操作顺序没有影响。

如果 \(x, y\) （在原图上）不相连，那么就是两个独立进行的合并过程，正确性显然。

如果 \(x, y\) （在原图上）相连，结果必定是使 \(S_x\) 与 \(S_y\) 合并成一个整体，其中 \(S_x, S_y\) 分别表示它们独立进行合并操作能得到的完全图点集。

对于多个连续操作点的情况可以类似分析。结论是——选定操作的点集，则结果与操作顺序无关。

也许还是很抽象，但是如果我把这个过程用另一个老朋友来介绍，那么前后文的所有内容都变得明朗起来：并查集。

回到我们的主线任务：求得到一个完全图点集 \(S\) 的最小操作次数。好了，既然与操作顺序无关，我们可以钦定一个方便我们进行 DP 的操作顺序。考察从一个初始点集 \(s\) 进行扩展到 \(S\)，可以断定：最优操作点集一定存在一个操作顺序，使得每次选定 \(s\) 内的点进行操作，并使 \(s\) 的大小至少增加 \(1\)。这用并查集仍然是好想的。

于是我们有了一个大致的算法流程：对于状态 \(f_S\)，枚举其内的点 \(i\) 进行操作，转移到新的点集 \(T\)，更新 \(f_T \xleftarrow{\min} f_S + 1\)。

还要记录具体方案？不难的，类似 \(f\) 的 DP 转移随便维护一下，最后回溯一遍即可。

下面是一些实现细节：

• 初始时，自己是认识自己的。
• 需要初始化所有完全图点集 \(S\)：\(f_S = 0\)。
• 记 \(c_i\) 表示 \(i\) 初始认识的点集。需要初始化所有非完全图点集 \(c_i\)：\(f_{c_i} = 1\)。

code CF906C Party

牢骚：此题完全配得上它的 *2400。我的理解不是非常深刻，远不如 CF 的官方题解。但是哪怕思考一下算法正确性的本质也是极好的——可是，那些几行潦潦写完状态和转移、贴了份代码就走人的题解，真的领悟到哪怕一点点此题的精华了吗？至少我将继续我的思考态度，并进一步加深......