题解 P3386 【【模板】二分图匹配】

2017-11-13 20:34:29


给两种做法:

  1. 匈牙利算法

本质上是贪心

#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.

最后在图上跑网络最大流即可。

#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;
}