给定一个包含 n n n 个点 m m m 条边的有向图,并给定每条边的容量,边的容量非负。
图中可能存在重边和自环。求从点 S S S 到点 T T T 的最大流。
第一行包含四个整数 n , m , S , T n,m,S,T n,m,S,T。
接下来 m m m 行,每行三个整数 u , v , c u,v,c u,v,c,表示从点 u u u 到点 v v v 存在一条有向边,容量为 c c c。
点的编号从 1 1 1 到 n n n。
输出点 S S S 到点 T T T 的最大流。
如果从点 S S S 无法到达点 T T T 则输出 0 0 0。
2
≤
n
≤
1000
2 \le n \le 1000
2≤n≤1000,
1
≤
m
≤
10000
1 \le m \le 10000
1≤m≤10000,
0
≤
c
≤
10000
0 \le c \le 10000
0≤c≤10000,
S
≠
T
S \neq T
S=T
不断 BFS,用 while
循环不断找残量网络中的增广路径。
每次
跳出循环即得出最大流。
AC Code
C + + \text{C}++ C++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 20010;
const int INF = 1e9;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], pre[N];
bool st[N];
inline void add(int a, int b, int c)
{
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}
bool bfs()
{
memset(st, false, sizeof st);
int hh = 0, tt = 0;
q[0] = S, d[S] = INF, st[S] = true;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j] && f[i])
{
st[j] = true;
d[j] = min(d[t], f[i]);
pre[j] = i;
if (j == T) return true;
q[ ++ tt] = j;
}
}
}
return false;
}
int EK()
{
int flow = 0;
while (bfs())
{
flow += d[T];
for (int i = T; i != S; i = e[pre[i] ^ 1])
f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
}
return flow;
}
int main()
{
int a, b, c;
memset(h, -1, sizeof h);
scanf("%d%d%d%d", &n, &m, &S, &T);
while (m -- )
{
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
printf("%d\n", EK());
return 0;
}
最后,如果觉得对您有帮助的话,点个赞再走吧!