原题链接

题意简述

求二分图的最大匹配。n≤100

题解

这里写的是匈牙利算法。

link[i]表示节点i的当前匹配。

used[i]为真表示在这一轮匹配中，无法给节点link[i]一个新的匹配。所以如果used[i]为真就不用再dfs它了，直接continue就好。

Code

//「网络流 24 题」搭配飞行员

#include <cstdio>

#include <cstring>

int const N=100+10;

int n,n1;

int cnt,h[N];

struct edge{int v,nxt;} ed[N*N];

void edAdd(int u,int v)

{

    cnt++; ed[cnt].v=v,ed[cnt].nxt=h[u],h[u]=cnt;

}

int link[N]; bool used[N];

bool Hungary(int u)

{

    for(int i=h[u];i;i=ed[i].nxt)

    {

        int v=ed[i].v;

        if(used[v]) continue;

        used[v]=true;

        if(!link[v] || Hungary(link[v])) {link[v]=u; return true;}

    }

    return false;

}

int main()

{

    scanf("%d%d",&n,&n1);

    while(true)

    {

        int u,v; if(scanf("%d%d",&u,&v)==EOF) break;

        edAdd(u,v);

    }

    int ans=0;

    for(int i=1;i<=n1;i++)

    {

        memset(used,0,sizeof used);

        if(Hungary(i)) ans++;

    }

    printf("%d\n",ans);

    return 0;

}