增广路
定义:
-
交错路始于非匹配点且由匹配边与非匹配边交错而成。
-
增广路是始于非匹配点且终于非匹配点(除了起始的点)的交错路。增广路中边的数量是奇数。
增广路上非匹配边比匹配边数量多 \(1\),如果将增广路上的匹配边和未匹配边反转,则匹配数量会增加 \(1\) 且依然是交错路。
二分图匹配
定义:一张二分图上的匹配称作二分匹配。
设 \(G\) 为二分图,若在 \(G\) 的子图 \(M\) 中,任意两条边都没有公共节点,那么称 \(M\) 为二分图 \(G\) 的一个匹配,且 \(M\) 的边数为匹配数。
二分图最大匹配
增广路算法
因为增广路长度为奇数,路径起始点非左即右,所以我们先考虑从左边的未匹配点找增广路。
因为交错路的关系,增广路上的第奇数条边都是非匹配边,第偶数条边都是匹配边,于是左到右都是非匹配边,右到左都是匹配边。 于是我们给二分图 定向,问题转换成:有向图中从给定起点找一条简单路径走到某个未匹配点,这个问题就等价于从点 \(x\) 能否走到终点 \(y\)。
那么只要从起始点开始 DFS 遍历直到找到某个未匹配点,\(O(m)\)。未找到增广路时,拓展的路也称为 交错树。
性质:因为要枚举 \(n\) 个点,总复杂度为 \(O(nm)\)。
代码实现:
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int match[N],vis[N],ans;
vector<int> q[N];
int dfs(int x){if(vis[x]) return 0;vis[x]=1;for(int i=0;i<q[x].size();i++){int y=q[x][i];if(!match[y]||dfs(match[y])){match[y]=x;return 1;}}return 0;
}
int main(){int n,m,t,u,v;cin>>n>>m>>t;while(t--){cin>>u>>v;q[u].push_back(v);}for(int i=1;i<=n;i++){memset(vis,0,sizeof vis);ans+=dfs(i);}cout<<ans;return 0;
}
例题:P3386 【模板】二分图最大匹配
二分图的判定
定义:不存在奇环的图是二分图。
判定方法:对图上遍历顺序相邻的两点着上相间的颜色,如果最后发现点的颜色关系不矛盾,则此图存在奇环,否则此图为二分图。
例题:T335415 0x68-二分图的判定-关押罪犯,T390010 0x68-二分图匹配-棋盘覆盖,T390013 0x68-二分图匹配-车的放置,T390014 0x68-二分图匹配-导弹防御塔,T390017 0x68-二分图匹配-蚂蚁