问题类型

如果一个图的点集可以分为两部分，且所有边的两个端点都在不同的部分中，则这个图是一个二分图。
有很多关于多选一的问题都可以建模成二分图来解决。
这里我们先讲关于二分图最大匹配的问题。

解决方案

首先我们来了解一些定义：
1.点覆盖集：即一个点集，使得所有边至少有一个端点在集合里。（“点”覆盖了所有“边”）
2.边覆盖集：即一个边集，使得所有点都与集合里的边邻接。（“边” 覆盖了所有“点”）
3.点独立集：即一个点集，满足集合中任两个结点不相邻。（导出的子图是零图（没有边）的点集）
4.边独立集：即一个边集，满足边集中的任两边不邻接。（就是匹配）
5.点支配集：即一个点集，使得所有其他点至少有一个相邻点在集合里。（一部分的“点”支配了所有“点”）。
6.边支配集：即一个边集，使得所有边至少有一条邻接边在集合里。（一部分的“边”支配了所有“边”）。
7.DAG的最小路径覆盖：是“路径” 覆盖“点”，即用尽量少的不相交简单路径覆盖有向无环图G的所有顶点，每个顶点严格属于一条路径。路径的长度可能为0(单个点)。

在二分图中，有以下性质：
1.最大匹配数 = 最大边独立数。
2.最大边独立数 = 最小点覆盖数 = 最大匹配数。
3.最大点独立数 = 最小边覆盖数 = n(节点个数) - 最大匹配数。
4.一个DAG的最小路径覆盖 = n(节点个数) - 转化为二分图后的最大匹配数

证明：
1.由定义即可知：最大匹配数 = 最大边独立数。
2.我们对最大匹配的每对匹配边都选取一个点出来组成点覆盖集。
证最小点覆盖≤最大匹配：如果仍有一些边未被这个集合覆盖，那么就说明匹配里可以加上这些未被覆盖的边，这就不是最大匹配了。
证最小点覆盖≥最大匹配：如果最大匹配里有一条边的两个点都不选，那么这条边就未被覆盖，不符合点覆盖的定义。
所以 最大边独立数 = 最小点覆盖数 = 最大匹配数。
3.我们先证明 最大点独立数 = n - 最大匹配数
最大点独立集其实就是最小点覆盖集关于整个二分图点集的补集。
先证明这是个点独立集：这些点之间如果还有边使独立集中两点相邻，则这条边就没被最小点覆盖集“覆盖”到，矛盾。
再证明这是个最大的点独立集：如果还能再加入点，这个点必定是最小点覆盖集中的一个点，而必定会有一条边联通这个点和原来的这个点独立集中的点，不符合点独立集定义。
所以就有 最大点独立数 = n - 最大匹配数。
我们再来证明 最小边覆盖 = n - 最大匹配数
假设最大匹配数为k。
我们贪心的考虑尽量用边去覆盖多的点，所以我们先把最大匹配都选了，已选k条边。
剩下n - 2 k个点都用一条边去覆盖，所以总共选了n - 2 k + k = n - k。
所以 最小边覆盖 = n - 最大匹配数。
4.我们先讲一下如何把一个DAG转化为一个二分图。
如果在DAG上u -> v有一条边，那我们在二分图上Xu -> Yv连一条边。
因为DAG的最小路径覆盖要求不能相交，所以每一个点最多只会有一个后继。
所以我们求出最大匹配后，那些在匹配里的就是有后继的节点，所以会有(n - 最大匹配数)个点没有后继节点。
又因为一条路径只会有一个点也就是最后一个点没有后继节点，所以 一个DAG的最小路径覆盖 = n - 转化为二分图后的最大匹配数。

有了以上性质，很多问题都可以转化为求二分图的最大匹配。接下来我们来讲讲如何求一个二分图的最大匹配。
所有求最大匹配的算法都是基于增广路定理的：一个匹配是最大匹配当且仅当没有增广路。这个定理适用于任意图。
我们先来讲一讲增广路的定义：增广路是一条起点为未匹配点，终点为未匹配点，且相邻两条边肯定满足一条在匹配里，一条不在匹配里的路径。
所以增广路有以下性质：
1.有奇数条边，有偶数个点。
2.起点在二分图的左半边，终点在右半边（一个左半边，一个右半边）。
3.路径上的点一定是一个在左半边，一个在右半边，交替出现。
4.整条路径上没有重复的点。
5.起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。
6.路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。
7.把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数多了1个。（求最大匹配的关键）

我们先来讲讲用匈牙利算法求二分图的最大匹配：
我们先给每个点都置为未匹配。每次我们都寻找到一条增广路的时候，答案+1即可。
那么如何寻找增广路呢？
我们先从随意一个未被匹配的点开始找起，遍历它的出边u -> v。
如果v没有匹配或者可以从v的匹配开始继续找到增广路（递归实现）那么就把v的匹配改成u（给匹配取反）。
因为增广路不能相交，所以一个点在同一个寻找增广路的过程中被扫过多次就没有意义了。用数组标记以下即可。
所以每次寻找增广路时间复杂度为O(m)。又因为最大匹配不超过n，即最多找n次增广路，所以总时间复杂度为O(n * m)。

Hopcroft-Karp算法就是对匈牙利算法进行了优化：匈牙利是每次找一条增广路，Hopcroft-Karp是每次找多条增广路。
我们用bfs来寻找还有没有增广路，顺便处理一个点到X点集中还未匹配过的点的最短距离。
所以我们dfs增广的时候只要对dis[v] = dis[u] + 1的边进行增广就可以了。
算法流程类似下图：

其中红色边为增广路，黄色边为已匹配的边。
好像可以证明时间复杂度是O(n ^ 0.5 * m)（但我不会啊）

代码演示

匈牙利算法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int Find(int u)
{
    travel(i, u)
    {
        int v = edge[i].vet;
        if (vis[v]) continue;
        vis[v] = 1;
        if (!match[v] || Find(match[v]))
        {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}
int main()
{
    Init();
    rep(i, 1, n)
    {
        if (match[i]) continue;
        rep(j, 1, n) vis[j] = 0;
        if (Find(i)) ans++;
    }
}

Hopcroft-Karp算法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

int bfs()
{
    rep(i, 1, n)
    {
        Disx[i] = Disy[i] = -1;
        if (!Matchx[i]) Q.push(i), Disx[i] = 0;
    }
    Dis = INF;
    while (!Q.empty())
    {
        int u = Q.front(); Q.pop();
        if (Disx[u] > Dis) continue;
        travel(i, u)
        {
            int v = edge[i].vet;
            if (~Disy[v]) continue;
            Disy[v] = Disx[u] + 1;
            if (!Matchy[v]) Dis = Disy[v];
            else
            {
                Disx[Matchy[v]] = Disy[v] + 1;
                Q.push(Matchy[v]);
            }
        }
    }
    return Dis != INF;
}

int dfs(int u)
{
    travel(i, u)
    {
        int v = edge[i].vet;
        if (!vis[v] && Disy[v] == Disx[u] + 1)
        {
            vis[v] = 1;
            if (!Matchy[v] || dfs(Matchy[v]))
            {
                Matchy[v] = u, Matchx[u] = v;
                return 1;
            }
        }
    }
    return 0;
}

int MaxMatch()
{
    int Match = 0;
    while (bfs())
    {
        rep(i, 1, n) vis[i] = 0;
        rep(i, 1, n) if (!Matchx[i]) Match += dfs(i);
    }
    return Match;
}