[Luogu3376]网络最大流

本文主要用于记录几种常用的最大流算法

$Dinic$

想看总结的戳这里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define INF 1000000009
using namespace std;
const int maxn=200002;
int m,n,s,t,w,x,y,z,ans,num=-1;
int cur[maxn],deep[maxn],head[maxn];
struct SX { int to,dis,from; } edge[maxn] ;
inline void Add(int from,int to,int dis) {
edge[++num].from=head[from];
edge[num].to=to;
edge[num].dis=dis;
head[from]=num;
}
inline bool Bfs(){
memset(deep,0,sizeof(deep));
queue < int > Q;
while(!Q.empty()) Q.pop();
Q.push(s); deep[s]=1;
while(!Q.empty()) {
int u=Q.front(); Q.pop();
for(register int i=head[u];i!=-1;i=edge[i].from) {
int v=edge[i].to;
if(deep[v]==0&&edge[i].dis>0) deep[v]=deep[u]+1,Q.push(v);
}
}
if(deep[t]) return true;
else return false;
}
inline int Dfs(int u,int f) {
if(u==t) return f;
for(register int &i=cur[u];i!=-1;i=edge[i].from) {
int v=edge[i].to;
if(deep[v]==deep[u]+1&&edge[i].dis>0) {
int d=Dfs(v,min(f,edge[i].dis));
if(d>0) {
edge[i].dis-=d;
edge[i^1].dis+=d;
return d;
}
}
}
return 0;
}
int main() {
memset(head,-1,sizeof(head));
scanf("%d%d%d%d",&n,&m,&s,&t);
for(register int i=1;i<=m;++i) {
scanf("%d%d%d",&x,&y,&z);
Add(x,y,z); Add(y,x,0);
}
while(Bfs()) {
for(register int i=1;i<=n;++i) cur[i]=head[i];
while(w=Dfs(s,INF)) ans+=w;
}
printf("%d\n",ans);
return 0;
}