テンプレートは非常に重要です。 以下に、いくつかの高速で短いネットワークフローのテンプレートを紹介します。
1. 最大フロー
a. HLPP
バージョン1:
このバージョンには激しい最適化が施されています。
行数: 46行 実行時間: 全体で44ms
#include <cstdio>
using namespace std;
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
char BB[1 << 15], *S = BB, *T = BB;
#define cchar register char
#define cint register int
#define cbool register bool
template<class TT> inline void cin(TT &x) {
static char c; static int y;
for (c = getchar(), x = 0, y = 1; c < 48 || 57 < c; c = getchar()) if (c == '-') y = -1;
for (; 48 <= c && c <= 57; c = getchar()) x = ((x + (x << 2)) << 1) + (c ^ '0');
x *= y;
}
void outint(int x) { if (x >= 10) outint(x / 10); putchar(x % 10 + '0'); }
typedef int arr[10005];
typedef int ard[200005];
inline int min(cint a, cint b) { return a < b ? a : b; }
int tot = 1, n, qhead, tail;
arr head, cur, num, dis, pre, Q;
ard c, to, next;
void ae(cint u, cint v, cint w) {
c[++tot] = w; to[tot] = v;
next[tot] = head[u]; head[u] = tot;
}
int ar(cint s, cint t) {
cint flow = 1e9, p;
for (p = t; p != s; p = to[pre[p] ^ 1]) flow = min(flow, c[pre[p]]);
for (p = t; p != s; p = to[pre[p] ^ 1]) c[pre[p]] -= flow, c[pre[p] ^ 1] += flow;
return flow;
}
void bfs(int s) {
cint now, p; Q[tail++] = s; dis[s] = 1;
while (qhead < tail) {
now = Q[qhead++];
for (p = head[now]; p; p = next[p])
if (!dis[to[p]]) dis[to[p]] = dis[now] + 1, Q[tail++] = to[p];
}
}
int MAXflow(cint s, cint t) {
cbool ok;
cint ans = 0, x = s, m, p, i; bfs(t);
for (i = 1; i <= n; i++) num[dis[i]]++;
for (i = 1; i <= n; i++) cur[i] = head[i];
while (dis[s] <= n) {
ok = false; if (x == t) ans += ar(s, t), x = s;
for (p = cur[x]; p; p = next[p])
if (c[p] > 0 && dis[x] == dis[to[p]] + 1) {
ok = true, cur[x] = p, pre[to[p]] = p, x = to[p]; break;
}
if (!ok) {
if (--num[dis[x]] == 0) break;
m = n;
for (p = head[x]; p; p = next[p])
if (c[p] > 0) m = min(m, dis[to[p]]);
num[dis[x] = m + 1]++; cur[x] = head[x];
if (x != s) x = to[pre[x] ^ 1];
}
}
return ans;
}
int main() {
cint a, b, c, m, s, t; cin(n), cin(m), cin(s), cin(t);
for (cint i = 0; i < m; i++) cin(a), cin(b), cin(c), ae(a, b, c), ae(b, a, 0);
outint(MAXflow(s, t)); return 0;
}
バージョン2:
行数: 50行 実行時間: 全体で610ms
実際のHLPPアルゴリズムを実装しています。
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1000015;
#define getchar() (W == C && (C = (W = BB) + fread(BB, 1, 1 << 15, stdin), W == C) ? EOF : *W++)
char BB[1 << 15], *W = BB, *C = BB;
template<class TT> inline void cin(TT &x) {
static char c; static int y;
for (c = getchar(), x = 0, y = 1; c < 48 || 57 < c; c = getchar()) if (c == '-') y = -1;
for (; 48 <= c && c <= 57; c = getchar()) x = ((x + (x << 2)) << 1) + (c ^ '0'); x *= y;
}
void outint(int x) { if (x >= 10) outint(x / 10); putchar(x % 10 + '0'); }
template<class T = int>
struct HLPP {
struct Node { int u, v, index; T c, f;
Node(int u, int v, int c, const T &f, const T &index) : u(u), v(v), c(c), f(f), index(index) {}
};
vector<Node> edge[MAXN]; vector<int> q[MAXN];
int dis[MAXN], cnt[MAXN + 1], pos, n; T exc[MAXN]; bool act[MAXN];
inline void addEdge(int u, int v, const T &c) {
edge[u].push_back(Node(u, v, c, 0, edge[v].size()));
if (u == v) edge[u].back().index++;
edge[v].push_back(Node(v, u, 0, 0, edge[u].size() - 1));
}
inline void enqueue(int v) {
if (!act[v] && exc[v] > 0 && dis[v] < n) act[v] = true, q[dis[v]].push_back(v), pos = max(pos, dis[v]);
}
inline void push(Node &e) {
register T amt = min(exc[e.u], e.c - e.f);
if (dis[e.u] == dis[e.v] + 1 && amt > 0)
e.f += amt, edge[e.v][e.index].f -= amt, exc[e.v] += amt, exc[e.u] -= amt, enqueue(e.v);
}
inline void gap(int k) {
for (register int v = 0; v < n; v++)
if (dis[v] >= k) cnt[dis[v]]--, dis[v] = max(dis[v], n), cnt[dis[v]]++, enqueue(v);
}
inline void relabel(int v) {
cnt[dis[v]]--; dis[v] = n;
for (register int i = 0; i < edge[v].size(); i++) {
Node *e = &edge[v][i];
if (e->c - e->f > 0) dis[v] = min(dis[v], dis[e->v] + 1);
}
cnt[dis[v]]++; enqueue(v);
}
inline void discharge(int v) {
for (register int i = 0; i < edge[v].size(); i++) {
Node &e = edge[v][i];
if (exc[v] > 0) push(e); else break;
}
if (exc[v] > 0) {
if (cnt[dis[v]] == 1) gap(dis[v]); else relabel(v);
}
}
inline T getMaxflow(int s, int t) {
pos = 0;
for (register int i = 0; i < edge[s].size(); i++) exc[s] += edge[s][i].c;
cnt[0] = n; enqueue(s); act[t] = true;
while (pos >= 0) {
if (!q[pos].empty()) {
register int v = q[pos].back(); q[pos].pop_back(); act[v] = false; discharge(v);
} else pos--;
}
return exc[t];
}
void init(int n) {
memset(edge, 0, sizeof(vector<Node>) * (n + 1));
memset(exc, 0, sizeof(T) * (n + 1));
memset(q, 0, sizeof(vector<int>) * (n + 1));
memset(act, 0, sizeof(bool) * (n + 1));
memset(cnt, 0, sizeof(int) * (n + 2));
memset(dis, 0, sizeof(int) * (n + 1));
this->n = n;
}
};
HLPP<> a;
int main() {
int n, m, s, t, t1, t2, t3;
cin(n), cin(m), cin(s), cin(t); a.init(n);
for (int i = 0; i < m; i++) cin(t1), cin(t2), cin(t3), a.addEdge(t1, t2, t3);
outint(a.getMaxflow(s, t));
}
バージョン3
行数: 40行 実行時間: 全体で608ms
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int s, t;
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
char BB[1 << 15], *S = BB, *T = BB;
#define cint register int
template<class TT> inline void cin(TT &x) {
static char c; static int y;
for (c = getchar(), x = 0, y = 1; c < 48 || 57 < c; c = getchar()) if (c == '-') y = -1;
for (; 48 <= c && c <= 57; c = getchar()) x = ((x + (x << 2)) << 1) + (c ^ '0'); x *= y;
}
void outint(cint x) { if (x >= 10) outint(x / 10); putchar(x % 10 + '0'); }
const int maxn = 10001;
const int maxm = 100001;
const int inf = 2147483646;
struct edge { int v, w, nxt; } e[maxm << 1];
int h[maxn], tot, d[maxn], n, m, prs[maxn], gap[maxn];
bool able[maxn];
void add(cint u, cint v, cint w) {
e[++tot] = (edge){v, w, h[u]}; h[u] = tot;
e[++tot] = (edge){u, 0, h[v]}; h[v] = tot;
}
struct cmp { int x, h;
cmp(cint x = 0, cint h = 0) : x(x), h(h) {}
inline bool operator<(const cmp &a) const { return h < a.h; }
};
priority_queue<cmp> pq;
bool push(cint x, cint y, cint p) {
cint w = min(prs[x], e[p].w);
e[p].w -= w, e[p ^ 1].w += w, prs[x] -= w, prs[y] += w;
return w;
}
void Gap(cint l, cint s, cint t) {
for (cint i = 1; i <= n; ++i)
if (i != s && i != t && l < d[i] && d[i] <= n) d[i] = n + 1;
}
int maxflow(cint s, cint t) {
while (!pq.empty()) pq.pop();
memset(prs, 0, sizeof prs), memset(d, 0, sizeof d), memset(gap, 0, sizeof gap);
d[s] = n, prs[s] = inf, pq.push(cmp(s, d[s]));
while (!pq.empty()) {
cint x = pq.top().x; pq.pop();
if (!prs[x]) continue;
for (cint i = h[x], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
if ((x == s || d[x] == d[v] + 1) && push(x, v, i) && v != t && v != s)
pq.push(cmp(v, d[v]));
if (x != s && x != t && prs[x]) {
if (!(--gap[d[x]])) Gap(d[x], s, t);
++gap[++d[x]];
pq.push(cmp(x, d[x]));
}
}
return prs[t];
}
int main() {
int x, y, w; cin(n), cin(m), cin(s), cin(t); tot = 1;
for (int i = 1; i <= m; ++i) {
cin(x), cin(y), cin(w);
if (!w) continue;
add(x, y, w);
}
int ans = maxflow(s, t);
outint(ans); return 0;
}
b. SAP
行数: 36行 実行時間: 全体で31ms
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 10010
#define MAXM 200010
#define INF 1073741823
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
char BB[1 << 15], *S = BB, *T = BB;
using namespace std;
int n, m, A, B, C, sz = 1, s, t;
int to[MAXM], v[MAXM], pre[MAXM], las[MAXN], H[MAXN], cur[MAXN], gap[MAXN];
queue<int> Q;
int inline read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
void outint(int x) { if (x >= 10) outint(x / 10); putchar(x % 10 + '0'); }
void ins(int a, int b, int c) {
sz++; to[sz] = b; v[sz] = c; pre[sz] = las[a]; las[a] = sz;
sz++; to[sz] = a; v[sz] = 0; pre[sz] = las[b]; las[b] = sz;
}
void bfs() {
Q.push(t); memset(H, -1, sizeof(H)); memset(gap, 0, sizeof(gap));
H[t] = 0; gap[0] = 1;
while (!Q.empty()) {
int tmp = Q.front(); Q.pop();
for (int i = las[tmp]; i; i = pre[i])
if (H[to[i]] == -1) H[to[i]] = H[tmp] + 1, gap[H[to[i]]]++, Q.push(to[i]);
}
}
int dfs(int x, int F) {
if (x == t) return F;
int used = 0, w;
for (int i = cur[x]; i; i = pre[i])
if (v[i] > 0 && H[to[i]] + 1 == H[x]) {
w = min(v[i], F - used), w = dfs(to[i], w);
v[i] -= w, v[i ^ 1] += w, used += w;
if (v[i] > 0) cur[x] = i;
if (F == used) return F;
}
gap[H[x]]--;
if (!gap[H[x]]) H[s] = n + 2;
gap[++H[x]]++; cur[x] = las[x]; return used;
}
int SAP() {
int ans = 0; for (int i = 1; i <= n; i++) cur[i] = las[i];
while (H[s] < n + 2) ans += dfs(s, INF);
return ans;
}
int main() {
n = read(), m = read(), s = read(), t = read();
for (int i = 1; i <= m; i++) A = read(), B = read(), C = read(), ins(A, B, C);
bfs(); outint(SAP()); return 0;
}
c. Dinic
少し最適化されたバージョン
行数: 48行 実行時間: 全体で47ms
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n, m, s, t, cnt, cur[10002], head[10002], num[10002], gap[10002];
int a[10002], fa[10002], Min[10002], d[10002], ans, q[10002], l;
bool f[10002];
int ch_top = 1e7;
char ch[10000000], *now_r = ch;
typedef struct { int flow, cap, nex, to; } bian;
bian p[200002];
void add(int u, int v, int w) {
p[cnt].cap = w; p[cnt].to = v; p[cnt].nex = head[u]; head[u] = cnt++;
p[cnt].cap = 0; p[cnt].to = u; p[cnt].nex = head[v]; head[v] = cnt++;
}
void bfs(int s) {
memset(d, -1, sizeof(d)); l = 0; int u; d[t] = 0; q[l++] = t;
for (int i = 0; i < l; i++) {
u = q[i]; gap[d[u]]++;
for (int j = head[u]; j != -1; j = p[j].nex)
if (p[j ^ 1].cap > p[j ^ 1].flow && d[p[j].to] == -1)
d[p[j].to] = d[u] + 1, q[l++] = p[j].to;
}
}
int dfs() {
int now = s; a[now] = 0; Min[now] = 1e9;
while (1) {
ccj:
if (Min[now] && now != t && d[s] < n) {
if (!f[now]) f[now] = 1;
else cur[now] = p[cur[now]].nex;
for (int &i = cur[now]; i != -1; i = p[i].nex)
if (p[i].cap > p[i].flow && d[p[i].to] + 1 == d[now]) {
num[p[i].to] = i; a[p[i].to] = 0; fa[p[i].to] = now;
Min[p[i].to] = min(Min[now], p[i].cap - p[i].flow);
now = p[i].to; f[p[i].to] = 0; goto ccj;
}
}
if (Min[now] && now != t && d[s] < n) {
if (--gap[d[now]] == 0) d[s] = n;
else {
int Minn = n - 1;
for (int i = head[now]; i != -1; i = p[i].nex)
if (p[i].cap > p[i].flow) Minn = min(d[p[i].to], Minn);
gap[d[now] = Minn + 1]++; cur[now] = head[now]; f[now] = 0;
}
}
if (now == s) return a[s];
if (now == t) a[now] = Min[now];
p[num[now]].flow += a[now]; p[num[now] ^ 1].flow -= a[now];
a[fa[now]] += a[now]; Min[fa[now]] -= a[now]; now = fa[now];
}
}
int read() {
int x = 0;
while (*now_r < 48) ++now_r;
for (x = *now_r - 48; *++now_r >= 48;)
x = (x << 1) + (x << 3) + *now_r - 48;
return x;
}
int main() {
fread(ch, 1, ch_top, stdin);
n = read(); m = read(); s = read(); t = read();
memset(head, -1, sizeof(head)); int u, v, w;
for (int i = 0; i < m; i++) u = read(), v = read(), w = read(), add(u, v, w);
bfs(s);
for (int i = 1; i <= n; i++) { f[i] = 0; cur[i] = head[i]; }
while (d[s] < n) ans += dfs();
printf("%d", ans); return 0;
}
2. 最小費用最大フロー
SPFA
行数: 46行 実行時間: 全体で481ms
#include <bits/stdc++.h>
using std::min;
#define getchar() (W == C && (C = (W = BB) + fread(BB, 1, 1 << 15, stdin), W == C) ? EOF : *W++)
char BB[1 << 15], *W = BB, *C = BB;
template<class TT> inline void cin(TT &x) {
static char c; static int y;
for (c = getchar(), x = 0, y = 1; c < 48 || 57 < c; c = getchar()) if (c == '-') y = -1;
for (; 48 <= c && c <= 57; c = getchar()) x = ((x + (x << 2)) << 1) + (c ^ '0');
x *= y;
}
#define oo 1000000000
#define N 10100
#define M 200100
int n, m, S, T, i, x, y, f, c, t[N];
struct edge { int to, next, f, cost; } l[M]; int e;
#define add(x, y, f, c) { l[++e] = (edge){y, t[x], f, c}; t[x] = e; }
int g[N], tot, h[N], _t[N], base, now, rt, head[N], next[N], *dy[N];
#define fu(x, y) { dy[y] = &x; x = y; }
#define _fu(x, y) { dy[y] = x; *x = y; }
void merge(int &x, int y) {
if (g[x] < g[y]) { fu(next[y], head[x]) fu(head[x], y) }
else { fu(next[x], head[y]) fu(head[y], x); x = y; }
}
void merges(int &x) {
int y = next[x], r;
while (y) r = next[y], merge(x, y), y = r;
}
bool spfa() {
for (i = 1; i <= n; ++i) g[i] = oo; g[rt = T] = 0;
do {
x = rt; merges(rt = head[rt]);
dy[x] = 0; next[x] = head[x] = 0; base = g[x];
for (_t[x] = i = t[x]; i; i = l[i].next)
if (l[i ^ 1].f && g[y = l[i].to] > (now = base - l[i].cost + h[x] - h[y])) {
if (now > g[S]) continue;
g[y] = now;
if (y != rt) {
if (dy[y] != 0) _fu(dy[y], next[*dy[y]]);
else if (!rt) { rt = y; continue; }
merge(rt, y);
}
}
} while (rt);
if (g[S] == oo) return 0;
for (x = 1; x <= n; ++x) h[x] += g[x];
return 1;
}
bool in[N];
void outint(int x) { if (x >= 10) outint(x / 10); putchar(x % 10 + '0'); }
int ansf = 0, ansc = 0;
int dfs(int x, int f) {
if (x == T) return f;
in[x] = 1; int f0 = f, del, y;
for (int &i = _t[x]; i; i = l[i].next)
if (l[i].f && (!in[y = l[i].to]) && (l[i].cost == h[x] - h[y])) {
del = dfs(y, min(l[i].f, f));
l[i].f -= del; l[i ^ 1].f += del; f -= del;
if (!f) { in[x] = 0; return f0; }
}
in[x] = 0; return f0 - f;
}
int main() {
cin(n); cin(m); cin(S); cin(T); e = 1;
for (i = 1; i <= m; ++i) { cin(x); cin(y); cin(f); cin(c); add(x, y, f, c); add(y, x, 0, -c); }
while (spfa()) f = dfs(S, oo), ansf += f, ansc += f * h[S];
outint(ansf); putchar(' '); outint(ansc);
}