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