用最大流求二分图最大匹配

新建一个S,T作为源点 汇点，从S到集合1 所有点连一条容量是1的边，保证只能被选一次，对于集合1 与集合2 之间的边连一条集合一到集合2 的有向边 容量可以是正无穷。跑一下dinic算出来的最大流就是最大匹配数量

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=200010+1010*2;
int q[N],d[N],cur[N],h[N],f[M],ne[M],e[M],idx,n,m,S,T,n1,n2;
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}

bool bfs()
{
    memset(d,-1,sizeof d);
    int hh=0,tt=0;
    q[0]=S,cur[S]=h[S],d[S]=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}

int find(int u,int limit){
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];i!=-1&&flow<limit;i=ne[i])
    {
        int ver=e[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t) d[ver]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int r=0,flow;
    while(bfs()  )  while(flow=find(S,0x3f3f3f3f)) r+=flow;
    return r;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n1>>n2>>m;
    S=n1+n2+1,T=0;
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b+n1,0x3f3f3f3f);
    }
    for(int i=1;i<=n1;i++) add(S,i,1);
    for(int i=1;i<=n2;i++) add(i+n1,T,1);
    cout<<dinic()<<endl;
    return 0;
}