【题目描述】
X集合有n个点（编号1，2，3，……n），
Y集合有m个点（编号1，2，3，……m），
有k条边（任意一条边的两个端点，一个来自X集合，一个来自Y集合）
如果选中一个点（可以来自X集合或Y集合）就是燃烧掉所有与该点相连的边。
问：至少选中多少个点，可以摧毁所有边（也就是k条边）
【输入】
第一行三个整数n, m，k( 0< n, m < 10000，0< k < 100000）。
下来k行，每行两个整数 x，y，表示一条边，连接X集合中x点和Y集合的y点。

【输出】一个整数，为最少选中的点数目。

输入：
4 5
8
1 3
2 1
2 2
2 4
3 3
4 3
4 4
4 5
输出：
3

 

最少点覆盖所有边

中山市第一中学 沈楚炎

 

在oi和ACM比赛中，直接用最大二分匹配（匈牙利算法）解题的题目较少，往往披上一层“最小覆盖”的外衣（），这类题目从表面看好像跟最大二分匹配无关，然而应用König定理可以轻松解决这类问题，本文给出König定理的证明，并且应用König定理展示解题中基本的构图技巧。

阅读本文需要读者先理解二分图的概念并且掌握匈牙利算法。

最小点覆盖数：在二分图中选了一个点（X集合或Y集合都行）就相当于覆盖了以它为端点的所有边，求覆盖所有边所需的最少点数。

König定理：一个二分图中的最大匹配数等于这个图中的最小点覆盖数。

在证明定理之前，让我们先用它来解决例题1。

例题1：选点摧毁所有边

【题目描述】

X集合有n个点（编号1，2，3，……n），

Y集合有m个点（编号1，2，3，……m），

有k条边（任意一条边的两个端点，一个来自X集合，一个来自Y集合）

如果选中一个点（可以来自X集合或Y集合）就是燃烧掉所有与该点相连的边。

问：至少选中多少个点，可以摧毁所有边（也就是k条边）

【输入】

第一行三个整数n, m，k( 0< n, m < 100，0< k < 1000）。

下来k行，每行两个整数 x，y，表示一条边，连接X集合中x点和Y集合的y点。

【输出】一个整数，为最少选中的点数目。

输入：

4 5

8

1 3

2 1

2 2

2 4

3 3

4 3

4 4

4 5

输出：

3

【解析】：按题意构图后，用匈牙利算法求最大二分匹配数，就是答案！什么？什么？什么？不急，等我慢慢解释：为什么最大二分匹配数等于最小点覆盖数。

König定理证明：

虽然直接应用König定理可以解决许多最小覆盖的题目，但这类题难点往往在于构图，要做到灵活构图应用König定理，则对其证明需要有一定的了解。König定理的证明是建立在匈牙利算法操作细节上的，掌握匈牙利算法的全过程很重要。   
    假设二分图G分为左边X和右边Y两个互不相交的点集。G经过匈牙利算法后找到一个最大匹配M，则可知G中再也找不到一条增广路径。

    根据König定理从最大匹配边中选M个点。下来说明选点策略，再证明这个策略的正确性。

选点策略：

标记右边未匹配边的顶点，并从右边未匹配边的顶点出发，按照边：未匹配→匹配→未匹配→……的原则标记途中经过的顶点，则最后一条经过的边必定为匹配边（否则为增广路经）。重复上述过程，直到右边不再含有未匹配边的点。

记得到的左边已标记的点和右边未标记的点为S， 以下证明S即为所求的最小顶点集。

证明选点策略：

  1、| S | 等于 M

左边标记的点全都为匹配边的顶点，右边未标记的点也为匹配边的顶点。因此，我们得到的点与匹配边一一对应。

  2、S能覆盖G中所有的边。

    根据左右端点是否被标记，G中所有的边有以下四种情况：

    ① 左右均标记；

    ② 左右均无标记；

    ③ 左边标记，右边未标记；

    ④ 左边未标记，右边标记；

    前三种，S中点（包含：左边的点（标记）+右边的点（未标记））都能得到的，除了④。下面证明④不存在。

    假如存在一条边e不属于S所覆盖的边集，且e 左边未标记右边标记。

如果e不属于匹配边，那么左端点就可以通过这条边右端点到达（从而得到标记）；

如果e属于匹配边，那么右端点的标记从哪里来？它的标记只能是从这条匹配边的左端点过来，那么左端点就应该有标记。

  3、S是最小的覆盖。

    因为最大匹配M中，M条边两两之间没有共同交点，所以要覆盖这M条匹配边至少就需要M个点。

证毕。

总结：如果你真的超级无敌懒（严重不推荐），那就记住以下结论（如果你理解了以上证明，也要背以下结论）：

1、要摧毁所有边，选“最大匹配数”个点。（做题建造模型的时候要着重思考什么当成边，什么当成点）

2、扩展，选最少的点消失，让X集合和Y集合失去联系，哈哈，提醒这个是为了以后网络流的最小割做点不知道会起什么作用的铺垫。