二分图
二分图
前置知识
定义： 一个无向图，可以分成两个互不相交的点集
判定： 至少有两个节点，没有奇环
二分图最大匹配： 选出尽可能多的边，使得每个点仅被不超过一条边覆盖
二分图最小点覆盖： 选出尽可能少的点，使得每条边被覆盖
二分图最大独立集： 选出尽可能多个点，使得每个点之间没有边相连
二分图最大团： 选出尽可能多个点，构成一张完全图（二分图的补图上的最大独立集就是原图的最大团）
相关计算方法
二分图最大匹配
匈牙利算法
一些定义
匹配边： 在二分图中在两个点集之间连接的边，匹配边两端都是匹配点。
未匹配边： 在二分图中在两个点集之间连接的边，未匹配边一端是未匹配点一端是匹配点。
增广路： 在二分图中从未匹配点开始，按照未匹配边，匹配边交替的模式找到一个未匹配点结束。
在执行匈牙利算法时，就是从每个点出发，尝试寻找一条增广路，把路径上的所有原匹配点的匹配方向取反，即可得到匹配边数+1的方案
代码如下
bool dfs(int x){
for (int i=head[x];i;i=Pth[i].Next){
int y=Pth[i].y;
if (!vis[y]){
vis[y]=1;
if (!match[y] || dfs(match[y])){
match[y]=x;
return 1;
}
}
}
return 0;
}
//main
int ans=0;
for (int i=1;i<=n;++i){
memset(vis,0,sizeof vis);
if (dfs(i)) ans++;
}二分图最小点覆盖
定理： 二分图最小点覆盖等于二分图最大匹配
理解：
1. 首先可以发现，最小点覆盖一定>=最大匹配（因为最大匹配的所有边都是没有共同点的，至少每条边选出一个顶点）
2. 此时不可能存在有一条边两端都没有被选中，否则存在一条长为1的增广路，与最大匹配的定义矛盾
3. 因此二分图最小点覆盖等于二分图最大匹配
二分图最大独立集
定理： 二分图最大独立集等于二分图两侧点数-二分图最大匹配
理解： 想要所有的点全部不相连，就得删除某些点，可以发现，删除最小点覆盖的那些点时，正好满足条件，且不可能有更好的方案
DAG最小路径覆盖
概念：
DAG最小不相交路径点覆盖： 选出尽量少的若干路径，使得DAG所有点被路径经过，且每个点仅被覆盖一次
DAG最小可相交路径点覆盖： 选出尽量少的若干路径，使得DAG所有点被路径经过，每个点可被覆盖多次
有向图的拆点二分图： 把有向图的每个点$V$拆成$V_x$，$V_y$（x为左部节点，y为右部节点），对于一条边$(a,b)$，在二分图中连接$(a_x,b_y)$
可以发现， DAG最小不相交路径点覆盖 = DAG的点数-拆点二分图的最大匹配数
理解： 可以发现，每找到一组匹配边，就相当于把两条路径连接成一条路径，因此不难看出
DAG最小可相交路径点覆盖由于路径可以相交，因此先对原图做传递闭包，可以转化为不相交路径覆盖来做
一些例题
机器任务安排二分图最小点覆盖
泥泞的区域(muddy)分成行泥泞块和列泥泞块，对于每个点，连接它所在的行泥泞块和列泥泞块，二分图最小点覆盖
骑士放置(horse)对格子进行黑白染色，可以发现是个二分图，把可以互相攻击的骑士连边，二分图最大独立集
vani和cl2捉迷藏(travel) 先进行传递闭包，然后发现任意可见的两点只能选出一个点，二分图最大独立集
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/%E4%BA%8C%E5%88%86%E5%9B%BE/
