题面：

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

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

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

然后就去跑最大流。

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

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #define min(a,b) ((a)<(b)?(a):(b)) 5 using namespace std; 6 const int maxn=1050,maxm=maxn,maxe=maxm*maxn; 7 int N,M,u,v,E,num_edge=-1,edge_head[maxn+maxm],Q[maxn+maxm],f1,f2,Dep[maxn+maxm]; 8 int S,T,Cur[maxn+maxm]; 9 struct Edge{
   int to,nx,dis;}edge[maxe];10 inline void Add_edge(int from,int to,int dis){11     edge[++num_edge].nx=edge_head[from];12     edge[num_edge].to=to;13     edge[num_edge].dis=dis;14     edge_head[from]=num_edge;15     return;16 }17 inline bool Bfs(){18     memset(Dep,0,sizeof(Dep));19     f1=f2=1;20     Dep[S]=1;21     Q[f2++]=S;22     while(f1
        
         0){42                 edge[i].dis-=p;43                 edge[i^1].dis+=p;44                 return p;45             }46         }47     }48     return 0;49 }50 inline int Dinic(){51     int ans=0;52     while(Bfs()){53         int toi=N+M+2;54         for(int i=1;i<=toi;i++)Cur[i]=edge_head[i];55         while(int k=Dfs(S,1<<30))ans+=k;56     }57     return ans;58 }59 int main(){60     memset(edge_head,-1,sizeof(edge_head));61     scanf("%d%d%d",&N,&M,&E);62     S=N+M+1;T=N+M+2;63     for(int i=1;i<=N;i++){64         Add_edge(S,i,1);65         Add_edge(i,S,0);66     }67     int toi=N+M;68     for(int i=N+1;i<=toi;i++){69         Add_edge(i,T,1);70         Add_edge(T,i,0);71     }72     for(int i=1;i<=E;i++){73         scanf("%d%d",&u,&v);74         if(v>M||u>N)continue;75         v+=N;76         Add_edge(u,v,1);77         Add_edge(v,u,0);78     }79     printf("%d\n",Dinic());80     return 0;81 }
        
       
      
     

---

By:AlenaNuna