二分图最大匹配学习总结
二分图的定义
如果无向图 \(G=(V,E)\) 的点集 \(V\) 可以分为两个集合 \(V_1,V_2\),使边集 \(E\) 都在 \(V_1\) 和 \(V_2\) 之间,并且 \(V_1\) 和 \(V_2\) 内部的点没有连边,则 \(G\) 是一个二分图。
图例:
匹配&最大匹配
匹配:给定一个图 \(G\) ,在 \(G\) 的一个子图 \(M\) 中,\(M\) 的边集 \(E\) 中的 任意两条边都不连接在同一个顶点上,则称 \(M\) 是 \(G\) 的一个匹配。
最大匹配:在所有匹配中 边数最多的 一个匹配称为图的最大匹配。
最大匹配算法
一般图
一般图的最大匹配:带花树算法(Blossom Algorithm),高斯消元。
一般图的最大权匹配:带权带花树。
二分图
匈牙利算法
增广路径:若P是图G中一条连通两个 未匹配顶点 的路径,并且属匹配边集M的边和不属M的边(即已匹配和未匹配的边)在P上 交替出现,则称P为相对于M的一条增广路径。
算法过程:不断在图中寻找增广路径,每找到一条连接两个 未盖点 之间的增广路径,就将增广路径上的边 取反(将增广路径上 本属于匹配边的边 从最大匹配中 删除,本 不属于匹配边的边加入 最大匹配)。
由于增广路径的特殊性质,在每次取反操作后,最大匹配的边数会 加1。
证明:由于增广路径的两端点都是未盖点,所以连接两端点的边原先 都不属于最大匹配。所以,增广路径上本不属于最大匹配的边比原属于最大匹配的边数量 多1。
代码实现
#include<stdio.h>
#include<vector>
#include<cstring>
const int N=505;
std::vector<int> v[N];
int n,m,match[N],p[N];
bool vis[N];
bool dfs(int u){
for(auto i:v[u]){
if(!vis[i]){
vis[i]=true;
if(!match[i]||dfs(match[i])){
match[i]=u;
return true;
}
}
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
int y;
while(x--) scanf("%d",&y),v[i].emplace_back(y);
}
int ans=0;
for(int i=1;i<=n;i++){
std::memset(vis,false,sizeof vis);
ans+=dfs(i);
}
printf("%d",ans);
return 0;
}
最大流
由于每个点只会 匹配一个点,所以可以用最大流模型转化求解。
设一个超级源点 \(s\) 和一个超级汇点 \(t\)。每次加一条边 \((x,y)\),我们都建 从 \(x\) 到 \(y\) 的一条流量为 \(1\) 的边。
在跑最大流之前,我们再 把 \(s\) 向所有属于 \(V_1\) 的点建一条流量为 \(1\) 的边,把所有属于 \(V_2\) 的点向 \(t\) 建一条流量为 \(1\) 的边。
最后使用最大流算法(如 \(EK\),\(Dinic\),\(ISAP\),\(HLPP\) 等)求解,最大流量即为二分图的最大匹配边数。
注意:最大流在建边时需建一条 流量为 \(0\) 的反向边。
代码实现
#include<stdio.h>//Dinic
#include<algorithm>
#include<queue>
const int N=1e6+5,inf=0x3f3f3f3f;
struct jie{int to,val,nxt;}a[N];
int n,m,e,s,t,head[N],cnt=1,now[N],depth[N];
void add(int x,int y,int z){
cnt++;
a[cnt].to=y;
a[cnt].val=z;
a[cnt].nxt=head[x];
head[x]=cnt;
}
bool bfs(){
for(int i=1;i<=n+m+2;i++) depth[i]=inf;
std::queue<int> q;
depth[s]=0,now[s]=head[s],q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=a[i].nxt){
if(a[i].val>0&&depth[a[i].to]==inf){
now[a[i].to]=head[a[i].to],depth[a[i].to]=depth[u]+1,q.push(a[i].to);
if(a[i].to==t) return true;
}
}
}
return false;
}
int dfs(int u,int sum){
if(u==t) return sum;
int k,flow=0;
for(int i=now[u];i&&sum>0;i=a[i].nxt){
now[u]=i;
if(a[i].val>0&&depth[a[i].to]==depth[u]+1){
k=dfs(a[i].to,std::min(sum,a[i].val));
if(!k) depth[a[i].to]=inf;
a[i].val-=k,a[i^1].val+=k;
flow+=k,sum-=k;
}
}
return flow;
}
int Dinic(){
int ans=0;
while(bfs()) ans+=dfs(s,inf);
return ans;
}
int main(){
scanf("%d%d%d",&n,&m,&e);
s=n+m+1,t=n+m+2;
for(int i=1;i<=n;i++) add(s,i,1),add(i,s,0);
for(int i=1;i<=m;i++) add(i+n,t,1),add(t,i+n,0);
int x,y;
while(e--) scanf("%d%d",&x,&y),add(x,y+n,1),add(y+n,x,0);
printf("%d",Dinic());
return 0;
}
/*
How can I use Dinic to solve it?
e.g.:
scanf("%d%d%d",&n,&m,&e);
s=n+m+1,t=n+m+2;
for(int i=1;i<=n;i++) add(s,i,1),add(i,s,0);
for(int i=1;i<=m;i++) add(i+n,t,1),add(t,i+n,0);
int x,y;
while(e--) scanf("%d%d",&x,&y),add(x,y+n,1),add(y+n,x,0);
printf("%d",Dinic());
warning:the number of 'cnt' must start of 1
*/