增广路
定义：
-
交错路始于非匹配点且由匹配边与非匹配边交错而成。
-
增广路是始于非匹配点且终于非匹配点（除了起始的点）的交错路。增广路中边的数量是奇数。
增广路上非匹配边比匹配边数量多 \(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-二分图匹配-蚂蚁