首页 > > 程序设计 > C/C++ >

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

2018-06-17 21:39:28来源：未知阅读 ()

题目背景

二分图

题目描述

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

输入输出格式

输入格式：

第一行，n,m,e

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

输出格式：

共一行，二分图最大匹配

输入输出样例

输入样例#1：复制

1 1 1
1 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<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 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 node
16 {
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<int>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 }