library/flow/Dinic.hpp
Depends on
Required by
Verified with
Code
#pragma once
// https://misawa.github.io/others/flow/dinic_time_complexity.html
#include "library/graph/WeightedGraph.hpp"
template <typename T> class Dinic {
struct EdgeInfo {
T cap;
int rev;
};
WeightedGraph<EdgeInfo> G;
std::vector<int> level, current_edge, out_deg;
int s, t;
std::vector<std::pair<int, int>> edge_memo;
std::queue<int> que;
void bfs() {
// level[v]を（容量正の辺による）sからの最短距離にする
// 到達出来なければ-1
std::ranges::fill(level, -1);
level[s] = 0;
que.emplace(s);
while (que.size()) {
int v = que.front();
que.pop();
for (const auto &e : G[v]) {
const auto &[cap, rev] = e.weight;
if (cap == 0 || ~level[e.to])
continue;
level[e.to] = level[v] + 1;
que.emplace(e.to);
}
}
}
T dfs(int v, T f) {
// vからtに最短路で水を流す fがvまで持ってこれた水量 流せた量が返り値
if (v == t)
return f;
for (int &i = current_edge[v]; i < G[v].size();
i++) { // このdfsで使わなかった辺は次のBFSまで使われることはない
auto &e = G[v][i];
auto &[cap, rev] = e.weight;
if (cap > 0 &&
level[v] <
level
[e.to]) { // bfsをしているのでlevel[v]<level[e.to]ならlevel[v]+1==level[e.to]
T d = dfs(e.to, std::min(f, cap));
if (d == 0)
continue;
cap -= d;
G[e.to][rev].weight.cap += d;
return d; // 一本流せたらreturn
}
}
return 0;
}
public:
Dinic() = default;
Dinic(int n, int s = 0, int t_ = -1)
: G(n), level(n), current_edge(n), out_deg(n, 0), s(s), t(t_) {
if (t < 0)
t = n - 1;
}
// 0-indexed で edge_id 番目に追加した辺に流した量を返す
T operator[](const int edge_id) const {
assert(G.is_prepared());
const auto &[from, id] = edge_memo[edge_id];
return G.edge[from][id].weight.cap;
}
// 辺を追加した順番に [from,to,流量]
std::vector<std::tuple<int, int, T>> all_edge() {
assert(G.is_prepared());
std::vector<std::tuple<int, int, T>> res;
res.reserve(edge_memo.size());
for (const auto &[v, id] : edge_memo) {
const auto &[to, from, weight] = G[v][id];
res.emplace_back(from, to, weight.cap);
}
return res;
}
void add_arc(int from, int to, T cap) {
G.add_arc(from, to, {cap, out_deg[to]});
G.add_arc(to, from, {0, out_deg[from]++});
edge_memo.emplace_back(to, out_deg[to]++);
}
T flow(T lim = std::numeric_limits<T>::max() / 2) {
if (!G.is_prepared())
G.build();
T fl = 0;
while (lim > 0) {
bfs();
if (level[t] < 0)
break;
std::ranges::fill(current_edge, 0);
while (true) {
T f = dfs(s, lim);
if (f == 0)
break;
fl += f;
lim -= f;
}
}
return fl;
}
T st_flow(int s_, int t_, T lim = std::numeric_limits<T>::max() / 2) {
s = s_;
t = t_;
return flow(lim);
}
};
#line 2 "library/flow/Dinic.hpp"
// https://misawa.github.io/others/flow/dinic_time_complexity.html
#line 2 "library/graph/WeightedGraph.hpp"
template <typename T> struct WeightedEdge {
WeightedEdge() = default;
WeightedEdge(int from, int to, T weight)
: from(from), to(to), weight(weight) {}
int from, to;
T weight;
operator int() const { return to; }
};
template <typename T> struct WeightedGraph {
int n;
using weight_type = T;
using edge_type = WeightedEdge<T>;
std::vector<edge_type> edges;
protected:
std::vector<int> in_deg;
bool prepared;
class OutgoingEdges {
WeightedGraph *g;
int l, r;
public:
OutgoingEdges(WeightedGraph *g, int l, int r) : g(g), l(l), r(r) {}
edge_type *begin() { return &(g->edges[l]); }
edge_type *end() { return &(g->edges[r]); }
edge_type &operator[](int i) { return g->edges[l + i]; }
int size() const { return r - l; }
};
class ConstOutgoingEdges {
const WeightedGraph *g;
int l, r;
public:
ConstOutgoingEdges(const WeightedGraph *g, int l, int r)
: g(g), l(l), r(r) {}
const edge_type *begin() const { return &(g->edges[l]); }
const edge_type *end() const { return &(g->edges[r]); }
const edge_type &operator[](int i) const { return g->edges[l + i]; }
int size() const { return r - l; }
};
public:
OutgoingEdges operator[](int v) {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
const ConstOutgoingEdges operator[](int v) const {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
bool is_prepared() const { return prepared; }
WeightedGraph() : n(0), in_deg(1, 0), prepared(false) {}
WeightedGraph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
WeightedGraph(int n, int m, bool directed = false, int indexed = 1)
: n(n), in_deg(n + 1, 0), prepared(false) {
scan(m, directed, indexed);
}
void resize(int n) { n = n; }
void add_arc(int from, int to, T weight) {
assert(!prepared);
assert(0 <= from and from < n and 0 <= to and to < n);
edges.emplace_back(from, to, weight);
in_deg[from + 1]++;
}
void add_edge(int u, int v, T weight) {
add_arc(u, v, weight);
add_arc(v, u, weight);
}
void add_arc(const edge_type &e) { add_arc(e.from, e.to, e.weight); }
void add_edge(const edge_type &e) { add_edge(e.from, e.to, e.weight); }
void scan(int m, bool directed = false, int indexed = 1) {
edges.reserve(directed ? m : 2 * m);
while (m--) {
int u, v;
std::cin >> u >> v;
u -= indexed;
v -= indexed;
T weight;
std::cin >> weight;
if (directed)
add_arc(u, v, weight);
else
add_edge(u, v, weight);
}
build();
}
void build() {
assert(!prepared);
prepared = true;
for (int v = 0; v < n; v++)
in_deg[v + 1] += in_deg[v];
std::vector<edge_type> new_edges(in_deg.back());
auto counter = in_deg;
for (auto &&e : edges)
new_edges[counter[e.from]++] = e;
edges = new_edges;
}
void graph_debug() const {
#ifndef __DEBUG
return;
#endif
assert(prepared);
for (int from = 0; from < n; from++) {
std::cerr << from << ";";
for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
std::cerr << "(" << edges[i].to << "," << edges[i].weight
<< ")";
std::cerr << "\n";
}
}
};
#line 5 "library/flow/Dinic.hpp"
template <typename T> class Dinic {
struct EdgeInfo {
T cap;
int rev;
};
WeightedGraph<EdgeInfo> G;
std::vector<int> level, current_edge, out_deg;
int s, t;
std::vector<std::pair<int, int>> edge_memo;
std::queue<int> que;
void bfs() {
// level[v]を（容量正の辺による）sからの最短距離にする
// 到達出来なければ-1
std::ranges::fill(level, -1);
level[s] = 0;
que.emplace(s);
while (que.size()) {
int v = que.front();
que.pop();
for (const auto &e : G[v]) {
const auto &[cap, rev] = e.weight;
if (cap == 0 || ~level[e.to])
continue;
level[e.to] = level[v] + 1;
que.emplace(e.to);
}
}
}
T dfs(int v, T f) {
// vからtに最短路で水を流す fがvまで持ってこれた水量 流せた量が返り値
if (v == t)
return f;
for (int &i = current_edge[v]; i < G[v].size();
i++) { // このdfsで使わなかった辺は次のBFSまで使われることはない
auto &e = G[v][i];
auto &[cap, rev] = e.weight;
if (cap > 0 &&
level[v] <
level
[e.to]) { // bfsをしているのでlevel[v]<level[e.to]ならlevel[v]+1==level[e.to]
T d = dfs(e.to, std::min(f, cap));
if (d == 0)
continue;
cap -= d;
G[e.to][rev].weight.cap += d;
return d; // 一本流せたらreturn
}
}
return 0;
}
public:
Dinic() = default;
Dinic(int n, int s = 0, int t_ = -1)
: G(n), level(n), current_edge(n), out_deg(n, 0), s(s), t(t_) {
if (t < 0)
t = n - 1;
}
// 0-indexed で edge_id 番目に追加した辺に流した量を返す
T operator[](const int edge_id) const {
assert(G.is_prepared());
const auto &[from, id] = edge_memo[edge_id];
return G.edge[from][id].weight.cap;
}
// 辺を追加した順番に [from,to,流量]
std::vector<std::tuple<int, int, T>> all_edge() {
assert(G.is_prepared());
std::vector<std::tuple<int, int, T>> res;
res.reserve(edge_memo.size());
for (const auto &[v, id] : edge_memo) {
const auto &[to, from, weight] = G[v][id];
res.emplace_back(from, to, weight.cap);
}
return res;
}
void add_arc(int from, int to, T cap) {
G.add_arc(from, to, {cap, out_deg[to]});
G.add_arc(to, from, {0, out_deg[from]++});
edge_memo.emplace_back(to, out_deg[to]++);
}
T flow(T lim = std::numeric_limits<T>::max() / 2) {
if (!G.is_prepared())
G.build();
T fl = 0;
while (lim > 0) {
bfs();
if (level[t] < 0)
break;
std::ranges::fill(current_edge, 0);
while (true) {
T f = dfs(s, lim);
if (f == 0)
break;
fl += f;
lim -= f;
}
}
return fl;
}
T st_flow(int s_, int t_, T lim = std::numeric_limits<T>::max() / 2) {
s = s_;
t = t_;
return flow(lim);
}
};
Back to top page
build/pch/stdc++.hpp