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

2021年09月15日 阅读数：6

## 输入输出样例

1 1 1
1 1

1

## 说明

n,m \leq 1000code

 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;
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];
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;
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();
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     }
64 }
65 int ans=0;
66 inline void Dinic()
67 {
68     while(BFS())
69     {
71         ans+=DFS(S,INF);
72     }
73
74 }
75 int main()
76 {
79     for(int i=1;i<=e;i++)
80     {
84     }
85     S=0,T=INF;
86     for(int i=1;i<=n;i++)
93 }