拆点技巧与FF保护策略：2023ECJTU校赛A题详解

在2023ECJTU校赛中，题目A."FF想吃糖果"涉及了一个经典的图论问题。给定一个无向图，要求找出最少删除多少个非度最高的点，使得图不再连通。这是一个结合了最小割和特殊规则的题目。 解题思路： 1. 理解问题本质： 首先，将问题转化为经典问题：求最小割。通常最小割是通过删除边来使图分离，但这里需要转换为删除点。为实现这一目标，引入了“拆点”技巧，即将一个点分裂成两个点，用一条权重为1的边连接它们。这样，删除这条边就相当于删除了原来的点。 2. 处理特殊规则： `FF`的角色限制了可以删除的点，即不能删除与其他人联系最多的人。解决方法是通过修改图结构，将拆分点的中间边权重设置为无穷大（或新建一条权重无穷大的边），这样可以确保不会被`FF`保护的点被删除。 3. 利用算法： 利用最大流/最小割原理，如 Dinic 算法，找到图中的一个最小割。由于题目要求的是非度最高的点，这要求在求解最小割时，排除掉度最高的点。这可以通过预处理阶段确定哪些点不能被删除，然后在实际求解过程中只对其他点进行操作。 代码实现： C/C++代码示例展示了如何运用这些技巧，包括包含必要的头文件和核心的最小割算法。这段代码没有完全展示，但读者可以参考提供的伪代码框架，结合 Dinic 算法进行具体实现。 总结来说，本题关键在于理解最小割问题的转换和特殊角色的处理，以及有效地应用图论算法来解决。通过拆点、权值设置和特殊条件的处理，可以巧妙地避开`FF`的限制，找到所需的最少删除点数。