const int INF int 1e9 const int 1000 const int 10000 const int Q_SZ 10

 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
const int INF = (int) 1e9;
const int N = 1000;
const int M = 10000;
const int Q_SZ = 1023;
int cap[M], cost[M], linke[M], dest[M];
int dist[N], phi[N], from[N], head[N];
bool used[N];
int n, S, T, ffree = 0;
void add_arc(int u,int v,int CAP,int COST);// ~CAP=0,~COST=-COST
void build_graph() {/* S = n - 2, T = n - 1 */}
int dijkstra() {
forn (i, n) dist[i] = INF;
forn (i, n) used[i] = false;
dist[S] = 0;
forn (i, n) {
int u = -1;
forn (j, n) if (!used[j] && (u==-1 || dist[j] < dist[u])) u = j;
used[u] = true;
for (int arc = head[u]; arc != -1; arc = linke[arc]) {
if (cap[arc] == 0) continue;
int v = dest[arc];
int d = dist[u] + (phi[u] - phi[v]) + cost[arc];
if (d < dist[v]) dist[v] = d, from[v] = arc;
}
}
return dist[T] + phi[T];
}
void ford_belman() {
static int q[Q_SZ + 1];
int qh = 0, qt = 0;
forn (i, n) phi[i] = INF;
forn (i, n) used[i] = false;
phi[S] = 0;
q[qt++] = S;
used[S] = true;
while (qh != qt) {
int u = q[qh++];
qh &= Q_SZ;
used[u] = false;
for (int arc = head[u]; arc != -1; arc = linke[arc]) {
if (cap[arc] == 0) continue;
int v = dest[arc];
int d = phi[u] + cost[arc];
if (d < phi[v]) {
phi[v] = d;
if (!used[v]) {
q[qt++] = v;
qt &= Q_SZ;
used[v] = true;
}
}
}
}
forn (i, n) if (phi[i] == INF) phi[i] = 0;
}
int add_path() {
int min_cap = INF;
for (int v = T; v != S; v = dest[from[v] ^ 1]) {
mn(min_cap, cap[from[v]]);
}
for (int v = T; v != S; v = dest[from[v] ^ 1]) {
cap[from[v]] -= min_cap;
cap[from[v] ^ 1] += min_cap;
}
return min_cap;
}
int mcmf() {
int res = 0;
ford_belman(); // or fill(phi, phi+n, 0) iff no neg cost in init G
while (true) {
int t = dijkstra();
if (t == INF + phi[T]) break;
forn (j, n) if (dist[j] != INF) phi[j] += dist[j];
res += add_path() * t;
}
return res;
}