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

时间：2022-07-06 23:38:23

题目背景

二分图

题目描述

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

输入输出格式

输入格式：

第一行，n,m,e

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

输出格式：

共一行，二分图最大匹配

输入输出样例

输入样例#1： 复制 
1 1 1

1 1
输出样例#1： 复制 
1

说明

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

因为数据有坑，可能会遇到 v>mv>m 的情况。请把 v>mv>m 的数据自觉过滤掉。

算法：二分图匹配

建一个超级源点S

建一个超级汇点T

连n条S到1-n的边

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

所有边的权值都是1

跑最大流

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int MAXN=*1e6;

 const int INF=0x7ffff;

 inline int read()

 {

     char c=getchar();int flag=,x=;

     while(c<''||c>'')    {if(c=='-')    flag=-;c=getchar();}

     while(c>=''&&c<='')     x=x*+c-,c=getchar();return x*flag;

 }

 struct node

 {

     int u,v,f,nxt;

 }edge[MAXN];

 int head[MAXN];

 int num=;

 inline void add_edge(int x,int y,int z)

 {

     edge[num].u=x;

     edge[num].v=y;

     edge[num].f=z;

     edge[num].nxt=head[x];

     head[x]=num++;

 }

 int n,m,e;

 int S,T;

 int deep[MAXN],cur[MAXN];

 inline bool BFS()

 {

     memset(deep,,sizeof(deep));

     deep[S]=;

     queue<int>q;

     q.push(S);

     while(q.size()!=)

     {

         int p=q.front();q.pop();

         for(int i=head[p];i!=-;i=edge[i].nxt)

             if(deep[edge[i].v]==&&edge[i].f)

                 deep[edge[i].v]=deep[p]+,q.push(edge[i].v);

     }

     return deep[T];

 }

 int DFS(int now,int nowflow)

 {

     if(nowflow<=||now==T)    return nowflow;

     int totflow=;

     for(int &i=cur[now];i!=-;i=edge[i].nxt)

     {

         if(deep[edge[i].v]==deep[now]+&&edge[i].f)

         {

             int canflow=DFS(edge[i].v,min(edge[i].f,nowflow));

             totflow+=canflow;

             nowflow-=canflow;

             edge[i].f-=canflow;

             edge[i^].f+=canflow;

             if(nowflow<=)    break;

         }

     }

     return totflow;

 }

 int ans=;

 inline void Dinic()

 {

     while(BFS())

     {

         memcpy(cur,head,sizeof(head));

         ans+=DFS(S,INF);

     }

 }

 int main()

 {

     memset(head,-,sizeof(head));

     n=read();m=read();e=read();

     for(int i=;i<=e;i++)

     {

         int x=read(),y=read();

         add_edge(x,y+n,);

         add_edge(y+n,x,);

     }

     S=,T=INF;

     for(int i=;i<=n;i++)

         add_edge(S,i,),add_edge(i,S,);

     for(int i=;i<=m;i++)

         add_edge(i+n,T,),add_edge(T,i+n,);

     Dinic();

     printf("%d",ans);

     return ;

 }

相关文章