今天我刷题了吗
搜索文档…
EK 算法
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int inf(0x3f3f3f3f);
7
const int maxn(1e3 + 10);
8
const int maxm(2e4 + 10);
9
int ecnt, head[maxn];
10
int mn[maxn], pre[maxn];
11
bool vis[maxn];
12
13
struct edge {
14
int to, flow, nxt;
15
} edges[maxm];
16
17
template<typename T = int>
18
inline const T read()
19
{
20
T x = 0, f = 1;
21
char ch = getchar();
22
while (ch < '0' or ch > '9') {
23
if (ch == '-') f = -1;
24
ch = getchar();
25
}
26
while (ch >= '0' and ch <= '9') {
27
x = (x << 3) + (x << 1) + ch - '0';
28
ch = getchar();
29
}
30
return x * f;
31
}
32
33
template<typename T>
34
inline void write(T x, bool ln)
35
{
36
if (x < 0) {
37
putchar('-');
38
x = -x;
39
}
40
if (x > 9) write(x / 10, false);
41
putchar(x % 10 + '0');
42
if (ln) putchar(10);
43
}
44
45
inline void addEdge(int u, int v, int w)
46
{
47
edges[ecnt].to = v;
48
edges[ecnt].flow = w;
49
edges[ecnt].nxt = head[u];
50
head[u] = ecnt++;
51
}
52
53
bool bfs(int src, int des)
54
{
55
queue<int> q;
56
memset(vis, false, sizeof vis);
57
q.push(src);
58
vis[src] = true;
59
mn[src] = inf;
60
while (not q.empty()) {
61
int u = q.front();
62
q.pop();
63
for (int i = head[u]; compl i; i = edges[i].nxt) {
64
int v = edges[i].to, w = edges[i].flow;
65
if (not vis[v] and w) {
66
vis[v] = true;
67
mn[v] = min(mn[u], w);
68
pre[v] = i;
69
if (v == des) {
70
return true;
71
}
72
q.push(v);
73
}
74
}
75
}
76
return false;
77
}
78
79
ll ek(int src, int des)
80
{
81
ll res = 0;
82
while (bfs(src, des)) {
83
res += mn[des];
84
for (int i = des; i not_eq src; i = edges[pre[i] xor 1].to) {
85
edges[pre[i]].flow -= mn[des];
86
edges[pre[i] xor 1].flow += des;
87
}
88
}
89
return res;
90
}
91
92
int main()
93
{
94
#ifndef ONLINE_JUDGE
95
freopen("input.txt", "r", stdin);
96
#endif
97
memset(head, -1, sizeof head);
98
int n = read(), m = read(), s = read(), t = read();
99
while (m--) {
100
int u = read(), v = read(), w = read();
101
addEdge(u, v, w);
102
addEdge(v, u, 0);
103
}
104
write(ek(s, t), true);
105
return 0;
106
}
Copied!
最近更新 11mo ago
复制链接