二分图小记
\(\sf{definition}\)
对于一个图 \(G=(V,E)\)，若能将 \(G\) 分为两个子图 \(G_1=(V_1,E_1),G_2=(V_2,E_2)\)，且满足 \(E_1=E_2=\emptyset,V_1\cap V_2=\emptyset,V_1 \cup V_2=V\)，那么这个图就是一个二分图，\(V_1\) 被称为二分图的左部点，\(V_2\) 被称为二分图的右部点。
\(\sf{determine}\)
判定定理 一个图 \(G\) 是二分图，当且仅当 \(G\) 不存在奇环，即经过奇数个点的简单环。
证明 考虑由 \(V_1\) 回到 \(V_1\) 的路径的环所在集合必然是 \(V_1 \rightarrow V_2 \rightarrow V_1 \rightarrow V_2 \rightarrow \dots \rightarrow V_1\)，显然因为第一个点等于最后一个点，所经过的点数必然是偶数个。
因此，可以通过染色算法来判定二分图，即将每个点和与该点相邻的点染成异色，若有冲突，则该图不是二分图。
代码：
void color(int now,int co){
vis[now]=co;
for(int i=0;i<g[now].size();++i){
int y=g[now][i];
if(!vis[y])color(y,3-co);
else if(vis[y]==vis[now])ok=1;
}
}
\(\sf{analysis}\)
二分图的最大匹配问题 给定一个二分图 \(G\)，求选出一些边，使得这些边没有公共顶点，且边的数量最大。
匈牙利算法 对于每个点 \(x\)，枚举其邻点 \(y\)。
对于 \(y\)：
-
若 \(y\) 已被访问，即 \(y\) 已经增广完毕，跳过。
-
若 \(y\) 没有匹配，则将 \(y\) 的匹配记为 \(x\)，增广 \(y\)。
-
若 \(y\) 有匹配 \(z\)，但是 \(z\) 仍能够继续增广，则同 2。
时间复杂度 \(\mathrm{O}(nm)\)。
代码：
bool mc(int x){
for(int i=0;i<d[x].size();++i){
int y=d[x][i];
if(!vis[y]){
vis[y]=1;
if(!p[y]||mc(p[y])){
p[y] = x;
return true;
}
}
}
return false;
}
网络流模型求解 考虑新建立超级源点 \(s,t\)，对于 \(\forall x\in V_1,f(s,x)=1\)，对于 \(\forall x\in V_2,f(x,t)=1\)，对于 \((u,v)\in E\) (默认 \(u\in V_1,v\in V_2\))，\(f(u,v)=1\)。
在原图跑最大流，增广完毕后剩余容量为 \(0\) 的，形如 \(f(u,v)\) 的边即是匹配边。
时间复杂度 \(\mathrm{O}(m\sqrt n)\)。
代码有点长，就不放了，反正板子网上一大堆。
二分图的最小点覆盖 选最少的点，满足每条边至少有一个端点被选。
König 定理 二分图的最小点覆盖 = 二分图的最大匹配。
证明略，见 OI-wiki。
二分图的最大独立集 选最多的点，满足两两之间没有边相连。
定理 二分图的最大独立集 = 点数 - 最小点覆盖。
证明 对于最小点覆盖，每个边至少被选了一个点，对于其补集，每个边最多被选了一个点，满足两两之间无边相连，同时这种情况一定为最优的。
二分图最大权匹配 二分图中边权和最大的匹配。
KM 算法 待更新。
费用流模型求解 在模型中跑最大费用最大流即可。
\(\sf{examples}\)
P1525 显然若二分图 \(G=(V,E)\)，那么其子图 \(G'=(V,E'),E'\subseteq E\) 也为二分图，按边权排序，二分答案，判定前 \(k\) 条边是否组成二分图。
P6185 令 \(c_i=a_i-b_i\)，则操作转化为如何使 \(\forall c_i=0\)。
\(2\) 操作具有传递性，因此若只含 \(2\) 操作，原图会分成一个个连通块，每个连通块都可以在满足其和不变的情况下对其元素任意加减。
加入含 \(1\) 操作的边，考虑若 \((u_1,v)=1,(v,u_2)=1\)，则可以通过 \(u_1,v\) 同加 \(1\)，\(v,u_2\) 同减 \(1\)，相当于 \((u_1,u_2)=2\)。也就是说，对于点 \(i\) 的所有邻点，他们属于一个连通块。
这就可以转换为二分图判定问题，如果该图不是二分图，则该图上的点一定同时属于 \(1\) 个连通块，在该块元素总和奇偶性不变情况下可以对元素任意加减（总和一定 \(+2\) 或 \(-2\) 或不变，那么奇偶性肯定不变）。
如果该图是二分图，则可以满足左部点总和减去右部点总和的差不变对图中元素任意加减（考虑 \(1\) 操作一定是对于两个集合的点进行，两边和同时 \(+1\)，\(-1\)，差不变）。
由于图不一定联通，对于每个联通子图，判定即可。
UVA1194 König 定理模板题，对于能在一个点上的操作一定贪心的同时执行，所以求的是二分图的最小点覆盖，注意特判 \(a_i=b_i=0\) 的情况。
P2764 将每个点拆成入点和出点，对于原图的边相当于 \(u\) 的出点向 \(v\) 的入点连边，则 DAG 的最小路径覆盖条数 \(=\ n\ -\) 最大匹配。
分析 每组路径覆盖可以理解为一个连通块，那么每组匹配相当于并查集的 merge 操作，每次匹配必定减少一个连通块，因为不可能相同连通块的边会 merge（贪心思考，在最优方案中肯定优先选了点更大的方案）。
最大权匹配比较难，而且优先度不高，有时间再写。
\(\sf{reference\ material}\)
-
https://www.oi-wiki.org
-
https://www.luogu.com.cn/blog/George-Plover/noi-online-ti-gao-zu-t1-xu-lie