forked from Punyaslok/snippets
-
Notifications
You must be signed in to change notification settings - Fork 0
/
mcmf_dijkstra.cpp
110 lines (92 loc) · 2.83 KB
/
mcmf_dijkstra.cpp
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// Min-cost max-flow (uses Dijkstra's algorithm)
//
// Given a directed weighted graph, source, and sink, computes the minimum cost
// of the maximum flow from source to sink.
// This version uses Dijkstra's algorithm and gives good performance on all
// kinds of graphs.
//
// To use, call init(n), then add edges using edge(x, y, c, w), and finally
// call run(src, sink).
//
// Functions:
// - init(n) initializes the algorithm with the given number of nodes
// - edge(x, y, c, w) adds an edge x->y with capacity c and weight w
// - run(src, sink) runs the algorithm and returns {total_cost, total_flow}
//
// Time complexity: O(V * E^2 log E)
//
// Constants to configure:
// - MAXV is the maximum number of vertices
// - MAXE is the maximum number of edges (i.e. twice the calls to function edge)
// - oo is the "infinity" value
namespace Mcmf {
const int MAXV = 1000100;
const int MAXE = 1000100;
const llint oo = 1e18;
int V, E;
int last[MAXV], how[MAXV]; llint dist[MAXV], pi[MAXV];
int next[MAXE], from[MAXE], adj[MAXE]; llint cap[MAXE], cost[MAXE];
struct cmpf {
bool operator () (int a, int b) const {
if (dist[a] != dist[b]) return dist[a] < dist[b];
return a < b;
}
};
set<int, cmpf> S;
void init(int n) {
V = n;
E = 0;
REP(i, V) last[i] = -1;
}
void edge(int x, int y, llint c, llint w) {
from[E] = x; adj[E] = y; cap[E] = c; cost[E] = +w; next[E] = last[x]; last[x] = E++;
from[E] = y; adj[E] = x; cap[E] = 0; cost[E] = -w; next[E] = last[y]; last[y] = E++;
}
pair<llint, llint> run(int src, int sink) {
llint total = 0;
llint flow = 0;
REP(i, V) pi[i] = oo;
pi[src] = 0;
for (;;) {
bool done = true;
REP(x, V) for (int e = last[x]; e != -1; e = next[e])
if (cap[e] && pi[adj[e]] > pi[x] + cost[e])
pi[adj[e]] = pi[x] + cost[e], done = false;
if (done) break;
}
for (;;) {
REP(i, V) dist[i] = oo;
S.clear();
dist[src] = 0;
S.insert(src);
while (!S.empty()) {
int x = *S.begin();
S.erase(S.begin());
if (x == sink) break;
for (int e = last[x]; e != -1; e = next[e]) {
if (cap[e] == 0) continue;
int y = adj[e];
llint val = dist[x] + pi[x] + cost[e] - pi[y];
if (val < dist[y]) {
S.erase(y);
dist[y] = val;
how[y] = e;
S.insert(y);
}
}
}
if (dist[sink] >= oo / 2) break;
llint aug = cap[how[sink]];
for (int i = sink; i != src; i = from[how[i]])
aug = min(aug, cap[how[i]]);
for (int i = sink; i != src; i = from[how[i]]) {
cap[how[i]] -= aug;
cap[how[i]^1] += aug;
total += cost[how[i]] * aug;
}
flow += aug;
REP(i, V) pi[i] = min(pi[i] + dist[i], oo);
}
return {total, flow};
}
}