二分图匹配（持续更新）
二分匹配核心算法：匈牙利算法（最大流的写法后续更新）
注意：匈牙利算法 也适用于 没有 强连通分量的 图的 最大匹配求值
先上匈牙利算法基础模板（求最大匹配数）
bool lj[MAXN][MAXN], vis[MAXN];
int link[MAXN];
int n;
bool find(int x) { //算法核心，深搜操作
for(int i=0; i<n; ++i) {
if(lj[x][i]&&!vis[i]) {
vis[i]=1;
if(link[i]==-1||find(link[i])) { //这个点没有关联或者它的关联点能找到别的关联
link[i]=x;
return 1;
}
}
}
return 0;
}
int main() {
int k;
cin>>n>>k;
for(int i=0; i<k; i++) {
int x, y;
cin>>x>>y;
lj[x][y]=1;
}
//以下正式开始匈牙利算法
int cnt=0;
memset(link,-1,sizeof(link));
for(int i=0; i<n; ++i) {
memset(vis,0,sizeof(vis));
if(find(i)) cnt++;
}
return 0;
}
二分匹配知识点
- 最大匹配数=最小点覆盖
- 最小路径覆盖=最大独立集
- 最大匹配数+最大独立集=V
常见模型
- 在二维平面上将坐标按X，Y当做两个分图， 而坐标则看作分图之间的边；
- 有时需要重建X，Y的定义，如HDOJ 1045
- 其他类型动动脑子就好。
查看10道真题和解析