无权二分图的最大匹配 Acwing.861 二分图的最大匹配
创建一个虚拟源点$S’$和一个虚拟汇点$T’$,从$S’$到所有左边的结点各连一条容量为 1 的有向边,再从所有右边结点各连一条容量为 1 的有向边到到$T’$,最后把左右两点集之间的每条边变成一条由左指向右的,容量为 1 的有向边。
从图中很容易看出,新图的最大流即为二分图的最大匹配。
下面给出代码 实际运行110 ms 匈牙利算法平均在220 ms
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 1010, M = 2e5+2*N + 10;
struct Edge{
int v,c,ne;
} e[M];
int n1,n2,m,S,T;
int h[N],idx = 1;
int d[N],cur[N];
void add(int a,int b,int c){
e[++idx] = {b,c,h[a]};
h[a] = idx;
}
bool bfs(){
memset(d,0,sizeof d);
d[S] = 1;
queue<int> q;q.push(S);
while(q.size()){
int u = q.front();
q.pop();
for(int i = h[u]; i != -1; i = e[i].ne){
int v = e[i].v;
if(!d[v] && e[i].c){
d[v] = d[u] + 1;
q.push(v);
if(v == T)return true;
}
}
}
return false;
}
LL dfs(int u,LL mf){
if(u == T)return mf;
LL sum = 0;
for(int i = cur[u]; i != -1;i = e[i].ne){
int v = e[i].v;
cur[u] = i;
if(d[v] == d[u] + 1 && e[i].c){
LL f = dfs(v,min(mf,(LL)e[i].c));
e[i].c -= f;
e[i^1].c += f;
sum += f;
mf -= f;
if(mf == 0)break;
}
}
if(sum == 0)d[u] = 0;
return sum;
}
LL dinic(){
LL flow = 0;
while(bfs()){
memcpy(cur,h,sizeof h);
flow += dfs(S,1e9);
}
return flow;
}
int main()
{
scanf("%d%d%d",&n1,&n2,&m);
memset(h,-1,sizeof h);
S = 0, T = n1 + n2 + 2;
while(m -- ) {
int a,b;
scanf("%d%d",&a,&b);
add(a,b + n1,1);
add(b + n1,a,0);
}
for(int i = 1; i <= n1; ++i)add(S,i,1),add(i,S,0);
for(int i = 1; i <= n2; ++i)add(i + n1,T,1),add(T,i + n1,0);
LL t = dinic();
printf("%lld\n",t);
return 0;
}