最少点覆盖所有边

by scy

在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个点。
  证毕。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
vector<int>G[N];
int match[N],chw[N],tps;
bool fi(int x)
{
    for(int y:G[x])
        if(chw[y]!=tps)
        {
            chw[y]=tps;
            if(match[y]==0||fi(match[y])==1)
            {
                match[y]=x;
                return 1;
            }
        }
    return 0;
}
int main()
{
    int n,m,k;scanf("%d%d%d",&n,&m,&k);
    for(int i=1,x,y;i<=k;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].emplace_back(y);
    }
    
    int ans=0;memset(match,0,sizeof(match));memset(chw,0,sizeof(chw));
    for(int i=1;i<=n;i++)
    {
        tps=i;
        if(fi(i))ans++;
    }
    printf("%d\n",ans);
    return 0;
}