二分图匹配
二分图匹配
前置知识——二分图
首先，要明白什么是二分图(又称作二部图)。
形象的描述一下，现在你是某市的市长，而一条大河从你的城市中心穿流而过。所以，你为了使你的城市交通遍历，促进城市发展，你决定在这条河上建桥，以连接河两岸的路口。
如上图，所有河上的桥和路口就组成了一个二分图。
二分图的定义：如果顶点 $V $ 可分割为两个互不相交的子集 $(A,B)$，并且图中的每条边 $(i，j)$ 所关联的两个顶点 $i$ 和 $j$ 分别属于这两个不同的顶点集 $(i \in A,j \in B)$，则称图G为一个二分图。简而言之，就是顶点集 $V$ 可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。
意思就说，你把一个图的顶点分到河的两岸，图上所有的边只能是桥，不能是陆地上的公路，即不能在河的一侧修建边。
区别二分图，关键是看点集是否能分成两个独立的点集。无向图G为二分图的充要条件是，$G$ 至少有两个顶点，且其所有环的长度均为偶数，不存在奇环。可以存在偶环，如上图 $2\rightarrow7\rightarrow3\rightarrow8\rightarrow2$ 就是一个偶环，但上图满足二分图。任何无回路的的图均是二分图。
**总结：**DFS/BFS，如发现奇环则不是二分图，否则是。
更简单的：因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。
最大匹配
**匹配：**从二分图中选择 $n$ 条边，保证没有任何一个顶点是两条或以上边的终点。
一个形象的事情：
现在你变身成为了月老，发现今天有 $n$ 个男生和 $m$ 个女生在你的庙(月老庙)前许愿求姻缘。你今天很高兴，决定帮帮他们。他们每个人祈祷的时候都说了他们心仪的对象，你将他们整理了一下，将可能(符合双方的要求 -__- )的两个人之间连一条线(假设没有gay)，建立了一个二分图。
这时候，作为善良的你，需要履行帮助人类繁衍生息的职责，因此要促成尽可能多的情侣狗，问最多能搞成几对？
数学表示：若 $E'\in E$，且 $E'$ 中任意两条边不共用同一个顶点，则称 $E'$ 是二分图 $G$ 的一个匹配。
**最大匹配：**边数最多的匹配(促成的情侣狗最多)。即 $E'$ 中边数最大。
**完美匹配：**所有向你求愿单身狗都变成了情侣狗。即 $E'=E$。
匈牙利算法——寻找最大匹配
交替路与增广路
**交替路：**从一个未匹配点出发，依次经过非匹配边、匹配边，并且第一条和最后一条边均为非匹配边，形成的路径叫交替路。
**增广路：**从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路。
-
红色的边为当前的匹配
-
紫色的边为当前匹配的增广路
-
将增广路中匹配的边和非匹配变交换，匹配边数 $+1$
匈牙利算法的真面目
匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。(看完的都是好宝宝)
简单一点，就是一个不断逼近答案的过程。
对于每个节点，执行如下步骤：
- 如果连接这个节点的任何一条边可以被选中，则将这条边加入匹配，返回TRUE。
- 如果莫得可以加入的边了，那么可以推导出连接它的所有边均为非匹配边。然后开始逐个寻找增广路，直到全部遍历完成(返回FALSE)或者把其中的某一条边加入匹配(即找到了一条增广路，返回TRUE)。
这个东西的烦人之处在于这玩意的代码………………难以理解，需得手推
#include <cstdio>
#include <bitset>
#include <vector>
const int maxe = 600;
int n, m, e, ans, pot[maxe]; //一共有n个男生,m个女生,共e条边,pot[i]表示第i个女生属于的男生编号
std::bitset<maxe> vis; //标记是否访问过(名花有主)
std::vector<int> con[maxe]; //以男生的角度记录这张图(因为要遍历男生找女生)
inline bool dfs(int now)
{
for (auto i : con[now]) //遍历他有好感的所有女生
{
if (!vis[i]) //如果这个女生现在莫得npy
{
vis[i] = 1; //表示你就是我的了
if (!pot[i] || dfs(pot[i])) //如果你原先没有npy或者前男友鱼塘里还有
{
pot[i] = now; //你现在彻底是我的了
return true; //表示我找到npy了(-_-)
}
}
}
return false; //我没有找到(T_T)
}
int main()
{
scanf("%d%d%d", &n, &m, &e);
for (int i = 0; i < e; i++)
{
int a, b;
scanf("%d%d", &a, &b);
con[a].push_back(b);
}
for (int i = 1; i <= n; i++)
{
vis.reset(); //每次都重新分配
if (dfs(i)) //如果现在的这个男生找到了npy,就又多了一对情侣
ans++;
}
printf("%d", ans);
return 0;
}
时间复杂度 $O(nm)$ 。
最大匹配的引申
最小边覆盖= n - 最大匹配
一个边集里的边能覆盖所有的点，最小边覆盖是满足这个要求的所有边集中边数最少的一个。
证明：
因为边数越小越好，则每条边能覆盖的点一定是越多越好(尽量每条边都覆盖2个点)，而最大匹配找出了最多覆盖2个点的边。而剩下的就只能一条边覆盖一个点了。
所以，设总顶点数为 $n$，最大匹配边为 $m$，则可以得到 $$ 最小边覆盖=m+(n-2m)=n-m $$
最小点覆盖 = 最大匹配
**最小点覆盖：**假如选了一个点就相当于覆盖了以它为端点的所有边。最小点覆盖就是选择最少的点来覆盖所有的边。
**证明：**由最大匹配可知，不存在一条边的两个端点均没有被在最大匹配集合中的边所连接的情况(否则这条边就可以加入匹配)。因此，我们可以将边分为两类：匹配边和非匹配边；也可以将点分为两类：是匹配边的端点和不是匹配边的端点。
如上图，匹配边，非匹配边，匹配边的端点，不是匹配边的端点。
在匹配边的端点中选择有相邻不是匹配边的端点的点即可。
这样的点保证之多有最大匹配个。
首先，我们只要没傻到在同一条匹配边上选择两个点就行，这样，所有的匹配边均可被覆盖。
同一条匹配边上的端点不可能同时与不是匹配边的端点相邻，否则构成一条增广路(如上图，若有11号节点与9号节点连接，则 $11\rightarrow9\rightarrow5\rightarrow10$ 构成增广路)。
因此，最小点覆盖 = 最大匹配。
最大独立集 = n - 最小点覆盖
选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。
**证明：**去掉最小点覆盖的顶点后，所有点之间不连通(因为删去最小点覆盖保证所有边均删除，因此不会出现连通)。