题解 P3386 【【模板】二分图匹配】
suncongbo
2017-11-13 20:34:29
给两种做法:
1. 匈牙利算法
本质上是贪心
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e3;
bool f[N][N];
bool used[N];
int match[N];
int n,m,e;
bool DFS(int pos)
{
for(int i=1; i<=m; i++)
{
if(f[pos][i] && !used[i])
{
used[i] = true;
if(!match[i] || DFS(match[i])) //如果这个点i还未匹配则pos和他匹配,如果这个点已经匹配,那么如果本来和他匹配的点match[i]还能找到另一个点匹配则pos把i“抢”过来,让match[i]去匹配另一个点,否则就不干涉i和match[i]匹配
{
match[i] = pos;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d%d",&n,&m,&e);
for(int i=1; i<=e; i++)
{
int x,y; scanf("%d%d",&x,&y);
if(x<=n && y<=m) f[x][y] = true;
}
int ans = 0;
for(int i=1; i<=n; i++)
{
memset(used,false,sizeof(used)); //注意此处
if(DFS(i)) ans++;
}
printf("%d\n",ans);
return 0;
}
```
2.网络最大流
建一个点s编号为1为源点,建一个点t编号为n+m+2为汇点。然后让A类点分别编号为2~n+1, B类点分别编号为n+2~n+m+1。
然后建边:把s和所有A类点都连边,AB类点之间根据输入连边,所有B类点和T连边,每条边边权均为1.
最后在图上跑网络最大流即可。
```cpp
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N = 2005;
const int M = 1002005;
const int INF = 0x7fffffff;
struct Edge
{
int v,val,nxt,rev;
};
Edge e[M<<1];
int fe[N];
queue<int> q;
int dep[N];
int n,m,s,t;
bool bfs()
{
while(!q.empty()) q.pop();
memset(dep,0,sizeof(dep));
q.push(s); dep[s] = 1;
while(!q.empty())
{
int c = q.front(); q.pop();
for(int i=fe[c]; i; i=e[i].nxt)
{
if(e[i].val>0 && !dep[e[i].v])
{
dep[e[i].v] = dep[c]+1;
q.push(e[i].v);
}
}
}
if(dep[t]) return true;
else return false;
}
int dfs(int pos,int cur)
{
if(pos==t) return cur;
int rst = cur;
for(int i=fe[pos]; i; i=e[i].nxt)
{
if(dep[e[i].v]==dep[pos]+1 && e[i].val>0 && rst)
{
int flow = dfs(e[i].v,min(e[i].val,rst));
if(flow>0)
{
e[i].val -= flow;
rst -= flow;
e[e[i].rev].val += flow;
}
}
}
return cur-rst;
}
int dinic()
{
int ans = 0;
while(bfs()) ans += dfs(s,INF);
return ans;
}
void addedge(int u,int v,int val,int rev)
{
e[++m].v = v; e[m].val = val; e[m].rev = rev;
e[m].nxt = fe[u]; fe[u] = m;
}
int main()
{
int n1,n2,m0; m = 0;
scanf("%d%d%d",&n1,&n2,&m0);
n = n1+n2+2;
for(int i=1; i<=m0; i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x<=n1 && y<=n2)
{
addedge(x+1,y+n1+1,1,m+2);
addedge(y+n1+1,x+1,0,m);
}
}
for(int i=1; i<=n1; i++)
{
addedge(1,i+1,1,m+2);
addedge(i+1,1,0,m);
}
for(int i=1; i<=n2; i++)
{
addedge(i+n1+1,n,1,m+2);
addedge(n,i+n1+1,0,m);
}
s = 1; t = n;
printf("%d\n",dinic());
return 0;
}
```