复习心得 - 二分图
以前写过一篇匈牙利（增广路）算法，现在系统复习一下二分图。
定义
就是两排点，同一排之间两两不连边的图。
判断
可能不完全连通，从每一个新的点开始黑白染色判断即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,col[N];
vector<int>e[N];
bool is;
bool dfs(int p,int pre){
if(!pre)
col[p]=1;
else col[p]=3-col[pre];
bool res=1;
for(auto v:e[p]){
if(!col[v])
res&=dfs(v,p);
else if(col[v]==col[p])
return 0;
}
return res;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
is=1;
for(int i=1;i<=n;i++)if(!col[i])
is&=dfs(i,0);
cout<<(is?"Yes":"No");
return 0;
}最大匹配
详见我写的匈牙利算法。
这里介绍一些别的方法。
这里补充一点概念：
二分图
- 如果
E' 中任意两条边没有相同节点，则E' 为G 的匹配，设其为M 。 - 我们取
\max |E'| 的E' 为最大匹配，其中|E'| 为G 的匹配数。 - 要是
|E'|=|V_1| ，即V_1 中所有点都找到匹配了，那么这个匹配为完备匹配。
当然我们还有概念（我之前看不懂的）：
-
交错路径：在
G 上的一条路径P 其中P_i\to P_{i+1} (1<i< |P|) 边与P_{i-1}\to P_i 边其中一条\in M ，一条\notin M 。- 例子：当前有匹配
\{1_1\to 1_2,2_1\to 3_2\} ，那么当前路径P=1_1\to 1_2\to 2_1\to3_2 是交错路径。
- 例子：当前有匹配
-
【重要】增广路径：首先
P 是交错路径。然后P_1 与P_{|P|} （起点与终点）都未被匹配。 这个东西的作用是M\oplus P （集合异或）更优。- 例子：
P=3_1\to3_2{\color{red}\to}2_1\to1_2{\color{red}\to}1_1\to 2_2 ，你会发现这其实是上面例子加上了两个新的点两条边，其中原有匹配就是\{1_1\to 1_2,2_1\to 3_2\} 。 - 证明
M\oplus P 更优： - 在增广路径
P 中，是匹配的边比不是匹配的边多1 条（匹配边间隔一个非匹配边）被影响的边是在路径上的匹配边（{\color{red}\to} ）它们不再是匹配边，而其他的边（\to ）成为了匹配边。 - 原先的匹配边为
n 条，则非匹配边为n-1 条，增加新的两条边让非匹配边变成n-1+2=n+1 条，比原先的匹配边多了1 条。 - 综上，增广路径
P 可以替换原先M ，变为M\oplus P ，会有1 贡献。
- 例子：
我们发现了增广路径的性质之后，自然想到如何匹配。
我们发现匈牙利本质就是找增广路。虽然这很慢，lol。
考虑枚举一个点作为增广路的起点（
就结束了。
代码
水文尼蜡。
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
int n,m,ee,U,V,npy[N],ncnt;
int found[N];
bool e[N][N];
bool dfs(int p){
for(int v=1;v<=m;v++)if(e[p][v]&&!npy[v]){
npy[v]=1;
if(!found[v]||dfs(found[v])){
found[v]=p;
return 1;
}
}
return 0;
}
int main(){
cin>>n>>m>>ee;
for(int i=1;i<=ee;i++){
cin>>U>>V;
e[U][V]=1;
}
for(int i=1;i<=n;i++){
memset(npy,0,sizeof(npy));
if(dfs(i))++ncnt;
}
cout<<ncnt;
return 0;
}最后，祝愿广大 OIer 早日找到 NPY
（虽然这不可能——From Anguei
trick: 把有向图