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
|
// Laufzeit: O(|V|^2*|E|)
// Knoten müssen von 0 nummeriert sein.
const int INF = 0x3FFFFFFF, MAXN = 500;
struct edge { int a, b; ll f, c; };
int n, m, pt[MAXN], d[MAXN], s, t;
vector<edge> e;
vector<int> g[MAXN];
ll flow = 0, lim;
queue<int> q;
void addEdge(int a, int b, ll c) {
g[a].push_back(e.size());
e.push_back(edge {a, b, 0, c});
g[b].push_back(e.size());
e.push_back(edge {b, a, 0, 0});
}
bool bfs() {
for (int i = 0; i < n; i++) d[i] = INF;
d[s] = 0;
q.push(s);
while (!q.empty() && d[t] == INF) {
int cur = q.front(); q.pop();
for (int i = 0; i < (int)g[cur].size(); i++) {
int id = g[cur][i], to = e[id].b;
if (d[to] == INF && e[id].c - e[id].f >= lim) {
d[to] = d[cur] + 1;
q.push(to);
}
}
}
while (!q.empty()) q.pop();
return d[t] != INF;
}
bool dfs(int v, ll flow) {
if (flow == 0) return false;
if (v == t) return true;
for (; pt[v] < (int)g[v].size(); pt[v]++) {
int id = g[v][pt[v]], to = e[id].b;
if (d[to] == d[v] + 1 && e[id].c - e[id].f >= flow) {
int pushed = dfs(to, flow);
if (pushed) {
e[id].f += flow;
e[id ^ 1].f -= flow;
return true;
}
}
}
return false;
}
// Nicht vergessen, s und t zu setzen!
void dinic() {
for (lim = (1LL << 62); lim >= 1;) {
if (!bfs()) { lim /= 2; continue; }
for (int i = 0; i < n; i++) pt[i] = 0;
int pushed;
while ((pushed = dfs(s, lim))) flow += lim;
}
}
|
