浅谈二分图及二分图最大匹配
Cute_Fish
·
·
个人记录
What is 二分图？
我们称这两个点集，一个叫左部，一个叫右部。左部中的点叫左部点；右部中的点叫右部点。
## 二分图最大匹配 - 匈牙利算法
解决二分图最大匹配问题一般使用匈牙利算法，本质是不断寻找增广路来扩大匹配数.
具体过程：
1\. 首先从任意的一个未配对的点 $u$ 开始，从点 $u$ 的边中任意选一条边（假设这条边是从 $u$->$v$）开始配对。如果点 $v$ 未配对，则配对成功，这是便找到了一条增广路。如果点 $v$ 已经被配对，就去尝试递归寻找 $v$ 的对象 $q$ 找一条新的增广路，以此类推。
2\. 如果刚才所选的边配对失败，那就要从点 $u$ 的边中重新选一条边重新去试。直到点 $u$ 配对成功或尝试过点 $u$ 的所有边为止。
3\. 接下来就继续对剩下的未配对过的点一一进行配对，直到所有的点都已经尝试完毕，找不到新的增广路为止。
# 
如图：
男 1 可以选择女 1 或女 2 作为对象
男 2 可以选择女 2 或女 3 作为对象
男 3 则只能选择女 2 为对象
首先我们从男 1 开始，这时发现女 1 没男朋友，匹配成功，匹配数加 1
然后搜男 2, 发现女 2 单身，匹配成功匹配数加 1
最后搜男 3, 这时发现女 2 已经有男朋友了，就给他的男朋友男 2 开导一下，然后搜男 2 发现女 3 是单着的直接绿了女 2 去找女 3, 女 2 被绿了就又单着了跟男 3 配对，匹配数 + 1.
搜完全部男生，最大匹配数为 3.
# 
**字丑勿喷 QAQ**
code
```cpp
inline bool dfs(int x){
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(!vis[v]){
vis[v]=1;
if(cp[v]==-1||dfs(cp[v])){//没有cp或她的cp有更好的选择
cp[v]=x;
return true;
}
}
}
return false;
}
inline int solve(){
int res=0;
memset(cp,-1,sizeof(cp));
for(int i=1;i<=n;i++){//搜男生
memset(vis,0,sizeof(vis));
if(dfs(i))res++;
}
return res;
}
```
## 判断是否是二分图
~~非常简单爆搜即可~~，注意到二分图有可以分成**两类东西**的特点，我们可以用染色法求解。
用 0 表示没有被染色，-1 表示黑色，1 表示白色，搜到一个节点后它的颜色就是当前节点颜色取反。如果一个图不是二分图就必然有矛盾 (不能分成两类), 当搜到一个节点已经有颜色了并且不是当前节点颜色取反后的颜色那就有矛盾了。
code
```cpp
inline bool dfs(int x,int cl){
color[x]=cl;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(color[v]==0){
bool tmp=dfs(v,-cl);
if(!tmp)return false;
}
else if(color[v]==color[x])return false;//矛盾
}return true;
}
```