洛谷 P3386 【模板】二分图匹配 Dinic版-白红宇

洛谷 P3386 【模板】二分图匹配 Dinic版

阅读量：5997 次

发布时间：2019-06-20

本文共 2242 字，大约阅读时间需要 7 分钟。

题目背景

二分图

题目描述

给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数

输入输出格式

输入格式：

第一行，n,m,e

第二至e+1行，每行两个正整数u,v，表示u,v有一条连边

输出格式：

共一行，二分图最大匹配

输入输出样例

输入样例#1：

1 1 11 1

输出样例#1：

说明

$\leq 1000n,m≤1000， 1 \leq u \leq n1≤u≤n， 1 \leq v \leq m1≤v≤m$

因为数据有坑，可能会遇到

算法：二分图匹配

建一个超级源点S

建一个超级汇点T

连n条S到1-n的边

连m条n+1-n+1+m到T的边

所有边的权值都是1

跑最大流

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int MAXN=3*1e6; 8 const int INF=0x7ffff; 9 inline int read()10 {11     char c=getchar();int flag=1,x=0;12     while(c<'0'||c>'9')    {
   if(c=='-')    flag=-1;c=getchar();}13     while(c>='0'&&c<='9')     x=x*10+c-48,c=getchar();return x*flag;14 }15 struct node16 {17     int u,v,f,nxt;18 }edge[MAXN];19 int head[MAXN];20 int num=0;21 inline void add_edge(int x,int y,int z)22 {23     edge[num].u=x;24     edge[num].v=y;25     edge[num].f=z;26     edge[num].nxt=head[x];27     head[x]=num++;28 }29 int n,m,e;30 int S,T;31 int deep[MAXN],cur[MAXN];32 inline bool BFS()33 {34     memset(deep,0,sizeof(deep));35     deep[S]=1;36     queue
          
           q;37 q.push(S);38 while(q.size()!=0)39 {40 int p=q.front();q.pop();41 for(int i=head[p];i!=-1;i=edge[i].nxt)42 if(deep[edge[i].v]==0&&edge[i].f)43 deep[edge[i].v]=deep[p]+1,q.push(edge[i].v);44 }45 return deep[T];46 }47 int DFS(int now,int nowflow)48 {49 if(nowflow<=0||now==T) return nowflow;50 int totflow=0;51 for(int &i=cur[now];i!=-1;i=edge[i].nxt)52 {53 if(deep[edge[i].v]==deep[now]+1&&edge[i].f)54 {55 int canflow=DFS(edge[i].v,min(edge[i].f,nowflow));56 totflow+=canflow;57 nowflow-=canflow;58 edge[i].f-=canflow;59 edge[i^1].f+=canflow; 60 if(nowflow<=0) break;61 }62 }63 return totflow;64 }65 int ans=0;66 inline void Dinic()67 {68 while(BFS())69 {70 memcpy(cur,head,sizeof(head));71 ans+=DFS(S,INF);72 }73 74 }75 int main()76 {77 memset(head,-1,sizeof(head));78 n=read();m=read();e=read();79 for(int i=1;i<=e;i++)80 {81 int x=read(),y=read();82 add_edge(x,y+n,1);83 add_edge(y+n,x,0);84 }85 S=0,T=INF;86 for(int i=1;i<=n;i++)87 add_edge(S,i,1),add_edge(i,S,0);88 for(int i=1;i<=m;i++)89 add_edge(i+n,T,1),add_edge(T,i+n,0);90 Dinic();91 printf("%d",ans);92 return 0;93 }