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
|
constexpr ll INF = 1LL << 60; // Größer als der maximale Fluss.
struct MinCostFlow {
struct edge {
int to;
ll f, cost;
};
vector<edge> edges;
vector<vector<int>> adj;
vector<int> pref, con;
vector<ll> dist;
const int s, t;
ll maxflow, mincost;
MinCostFlow(int n, int source, int target) :
adj(n), s(source), t(target) {};
void addEdge(int u, int v, ll c, ll cost) {
adj[u].push_back(sz(edges));
edges.push_back({v, c, cost});
adj[v].push_back(sz(edges));
edges.push_back({u, 0, -cost});
}
bool SPFA() {
pref.assign(sz(adj), -1);
dist.assign(sz(adj), INF);
vector<bool> inqueue(sz(adj));
queue<int> queue;
dist[s] = 0;
queue.push(s);
pref[s] = s;
inqueue[s] = true;
while (!queue.empty()) {
int cur = queue.front(); queue.pop();
inqueue[cur] = false;
for (int id : adj[cur]) {
int to = edges[id].to;
if (edges[id].f > 0 &&
dist[to] > dist[cur] + edges[id].cost) {
dist[to] = dist[cur] + edges[id].cost;
pref[to] = cur;
con[to] = id;
if (!inqueue[to]) {
inqueue[to] = true;
queue.push(to);
}}}}
return pref[t] != -1;
}
void extend() {
ll w = INF;
for (int u = t; pref[u] != u; u = pref[u])
w = min(w, edges[con[u]].f);
maxflow += w;
mincost += dist[t] * w;
for (int u = t; pref[u] != u; u = pref[u]) {
edges[con[u]].f -= w;
edges[con[u] ^ 1].f += w;
}}
void mincostflow() {
con.assign(sz(adj), 0);
maxflow = mincost = 0;
while (SPFA()) extend();
}
};
|
