Dinic二分图匹配 || Luogu P3386

题面：【模板】二分图匹配

思路：Dinic实现二分图匹配，要建一个超级源点（S）和超级汇点（T），分别定为N+M+1和N+M+2

然后S去和N中的数建正边和反边，正边权值为1，反边权值为0；M中的数去与T建正边和反边，正边权值为1。

N、M之间的数建图一样。

然后就去跑最大流。

注意：在Dinic函数中每次更新Cur的值时，要把S和T的Cur也更新了。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int maxn=1050,maxm=maxn,maxe=maxm*maxn;
int N,M,u,v,E,num_edge=-1,edge_head[maxn+maxm],Q[maxn+maxm],f1,f2,Dep[maxn+maxm];
int S,T,Cur[maxn+maxm];
struct Edge{int to,nx,dis;}edge[maxe];
inline void Add_edge(int from,int to,int dis){
    edge[++num_edge].nx=edge_head[from];
    edge[num_edge].to=to;
    edge[num_edge].dis=dis;
    edge_head[from]=num_edge;
    return;
}
inline bool Bfs(){
    memset(Dep,0,sizeof(Dep));
    f1=f2=1;
    Dep[S]=1;
    Q[f2++]=S;
    while(f1<f2){
        int x=Q[f1++];
        for(int i=edge_head[x];i!=-1;i=edge[i].nx){
            int y=edge[i].to;
            if(edge[i].dis&&Dep[y]==0){
                Dep[y]=Dep[x]+1;
                Q[f2++]=y;
            }
        }
    }
    if(Dep[T])return 1;
    return 0;
}
inline int Dfs(int x,int fw){
    if(x==T)return fw;
    for(int &i=Cur[x];i!=-1;i=edge[i].nx){
        int y=edge[i].to;
        if(Dep[y]==Dep[x]+1&&edge[i].dis){
            int p=Dfs(y,min(edge[i].dis,fw));
            if(p>0){
                edge[i].dis-=p;
                edge[i^1].dis+=p;
                return p;
            }
        }
    }
    return 0;
}
inline int Dinic(){
    int ans=0;
    while(Bfs()){
        int toi=N+M+2;
        for(int i=1;i<=toi;i++)Cur[i]=edge_head[i];
        while(int k=Dfs(S,1<<30))ans+=k;
    }
    return ans;
}
int main(){
    memset(edge_head,-1,sizeof(edge_head));
    scanf("%d%d%d",&N,&M,&E);
    S=N+M+1;T=N+M+2;
    for(int i=1;i<=N;i++){
        Add_edge(S,i,1);
        Add_edge(i,S,0);
    }
    int toi=N+M;
    for(int i=N+1;i<=toi;i++){
        Add_edge(i,T,1);
        Add_edge(T,i,0);
    }
    for(int i=1;i<=E;i++){
        scanf("%d%d",&u,&v);
        if(v>M||u>N)continue;
        v+=N;
        Add_edge(u,v,1);
        Add_edge(v,u,0);
    }
    printf("%d\n",Dinic());
    return 0;
}

---

By:AlenaNuna