二分匹配核心算法:匈牙利算法(最大流的写法后续更新)
注意:匈牙利算法 也适用于 没有 强连通分量的 图的 最大匹配求值
先上匈牙利算法基础模板(求最大匹配数)
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
- 其他类型动动脑子就好。