Acwing2171.EK求最大流 [操作系统入门]
地址 https://www.acwing.com/problem/content/description/2173/
给定一个包含 n 个点 m 条边的有向图，并给定每条边的容量，边的容量非负。图中可能存在重边和自环。求从点 S 到点 T 的最大流。
输入格式
第一行包含四个整数 n,m,S,T。
接下来 m 行，每行三个整数 u,v,c，表示从点 u 到点 v 存在一条有向边，容量为 c。
点的编号从
1 到 n。输出格式
输出点 S 到点 T 的最大流。
如果从点 S 无法到达点 T 则输出
0。数据范围
2≤n≤1000,1≤m≤10000,0≤c≤10000,S≠T
输入样例：
71417125
136
145
232
253
322
343
353
367
465
561
651
578
677
输出样例：
14
STL代码 我的 较慢
// 11135.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。//#include
<iostream>#include
<queue>#include
<memory.h>#include
<map>#include
<unordered_set>usingnamespace std;
/*
给定一个包含 n 个点 m 条边的有向图，并给定每条边的容量，边的容量非负。
图中可能存在重边和自环。求从点 S 到点 T 的最大流。
输入格式
第一行包含四个整数 n,m,S,T。
接下来 m 行，每行三个整数 u,v,c，表示从点 u 到点 v 存在一条有向边，容量为 c。
点的编号从 1 到 n。
输出格式
输出点 S 到点 T 的最大流。
如果从点 S 无法到达点 T 则输出 0。
数据范围
2≤n≤1000,
1≤m≤10000,
0≤c≤10000,
S≠T
输入样例：
7 14 1 7
1 2 5
1 3 6
1 4 5
2 3 2
2 5 3
3 2 2
3 4 3
3 5 3
3 6 7
4 6 5
5 6 1
6 5 1
5 7 8
6 7 7
输出样例：
14
*/
/*
4 5 1 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
//==============
50
*/
constint N = 10010;
constint M = 20010;
map<pair<int, int>, int> graphW;
unordered_set<int> g[N];
int n, m;
int S, T;
int ans = 0;
int d[N];
int pre[N];
int st[N];
void addEdge(intfrom, int to, int flow)
{
//数组记录两点之间的关系 使用哈希记录两点之间的流 加速查找
pair<int, int> p1 = make_pair(from, to);
graphW[p1] += flow;
pair<int, int> p2 = make_pair(to, from);
graphW[p2] += 0;
g[from].insert(to);
g[to].insert(from);
}
bool bfs()
{
memset(st, 0, sizeof(st));
queue<int> q;
q.push(S);
st[S] = 1;
d[S] = 100000010;
while (q.size()) {
int t = q.front(); q.pop();
for (auto ver : g[t]) {
pair<int, int> edge = make_pair(t,ver);
int f = graphW[edge];
if (!st[ver] && f) {
st[ver] = 1;
d[ver] = min(d[t], f);
pre[ver] = t;
if (ver == T) returntrue;
q.push(ver);
}
}
}
returnfalse;
}
int main()
{
cin >> n >> m >> S >> T;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
addEdge(a, b, w);
}
while (bfs())
{
ans += d[T];
intfrom = T; int to = pre[from];
while (1) {
pair<int, int> E = make_pair(from, to);
pair<int, int> revE = make_pair(to, from);
graphW[E] += d[T];
graphW[revE] -= d[T];
if (to == S) break;
from = to; to = pre[from];
}
}
cout << ans << endl;
return0;
}
作者：itdef
链接：https://www.acwing.com/file_system/file/content/whole/index/content/1121865/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
View Code
标答
1 #include <iostream>2 #include <cstring>
3 #include <algorithm>
4
5usingnamespace std;
6
7constint N = 1010, M = 20010, INF = 1e8;
8
9int n, m, S, T;
10int h[N], e[M], f[M], ne[M], idx;
11int q[N], d[N], pre[N];
12bool st[N];
13
14void add(int a, int b, int c)
15{
16 e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
17 e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
18}
19
20bool bfs()
21{
22int hh = 0, tt = 0;
23 memset(st, false, sizeof st);
24 q[0] = S, st[S] = true, d[S] = INF;
25while (hh <= tt)
26 {
27int t = q[hh ++ ];
28for (int i = h[t]; ~i; i = ne[i])
29 {
30int ver = e[i];
31if (!st[ver] && f[i])
32 {
33 st[ver] = true;
34 d[ver] = min(d[t], f[i]);
35 pre[ver] = i;
36if (ver == T) returntrue;
37 q[ ++ tt] = ver;
38 }
39 }
40 }
41returnfalse;
42}
43
44int EK()
45{
46int r = 0;
47while (bfs())
48 {
49 r += d[T];
50for (int i = T; i != S; i = e[pre[i] ^ 1])
51 f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
52 }
53return r;
54}
55
56int main()
57{
58 scanf("%d%d%d%d", &n, &m, &S, &T);
59 memset(h, -1, sizeof h);
60while (m -- )
61 {
62int a, b, c;
63 scanf("%d%d%d", &a, &b, &c);
64 add(a, b, c);
65 }
66
67 printf("%d
", EK());
68
69return0;
70}
71
72作者：itdef
73 链接：https://www.acwing.com/file_system/file/content/whole/index/content/1121865/
74来源：AcWing
75 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
View Code
在网站的题解
https://www.acwing.com/file_system/file/content/whole/index/content/1121865/
Acwing 2171. EK求最大流
以上是 Acwing2171.EK求最大流 [操作系统入门] 的全部内容， 来源链接： utcz.com/z/518844.html
