P3376 [模板]网络最大流[dinic]

题目描述

如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。

输入输出格式

输入格式:

第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)

输出格式:

一行,包含一个正整数,即为该网络的最大流。

输入输出样例

输入样例#1:

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40

输出样例#1:

50

题解

ek过不了,所以这里是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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
int n,m,s,t,d;
struct node
{
int v,id;
long long w;
} a[200100];//链式前向星
int p[10100];
int p1[10100];
int h[10100];
int U,V,W;
long long ans;
queue<int> q;
inline int read()
{
char ch=getchar();
int x=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x;
}
inline void add(int u,int v,int w)
{
d++;
a[d].v=v;a[d].w=w;a[d].id=p[u];p[u]=d;
}//加边
inline int bfs()//建层次图
{
memset(h,-1,sizeof(h));
while (!q.empty()) q.pop();
q.push(s);
h[s]=0;
while (!q.empty())
{
int u=q.front();q.pop();
for (int i=p[u];i;i=a[i].id)
{
int v=a[i].v;
if (h[v]==-1&&a[i].w>0)
{
h[v]=h[u]+1;
q.push(v);
}
}
}
return h[t]!=-1;
}
inline long long dfs(int u,long long low)
{
if (u==t||low==0) return low;//low为0就走不了了就退出
long long used=0;
for (int i=p1[u];i;i=a[i].id)
{
int v=a[i].v;
if (h[v]==h[u]+1)//只搜下一层的边
{
long long w=dfs(v,min(low-used,a[i].w));
a[i].w-=w;
a[i^1].w+=w;//更新
used+=w;
p1[u]=i;//当前弧优化
if (used==low) return used;//用完了就返回
}
}
if (used==0) h[u]=-1;//u到终点走不了了下次就不要走了
return used;
}
int main()
{
d=1;
n=read();m=read();s=read();t=read();
for (int i=1;i<=m;i++)
{
U=read();V=read();W=read();
add(U,V,W);add(V,U,0);//建边
}
while (bfs())//不断找
{
for (int i=1;i<=n;i++) p1[i]=p[i];
ans+=dfs(s,23333333333);
}
printf("%lld",ans);
return 0;
}