CompetitiveProgrammingCpp
This documentation is automatically generated by online-judge-tools/verification-helper
Test/Graph/Flow/Dinic.test.cpp
- View this file on GitHub
- Last update: 2025-06-09 16:27:38+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A
Depends on
Code
#define PROBLEM \
"https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A"
#include "./../../../Library/Graph/Flow/Dinic.hpp"
#include <iostream>
#include "./../../../Library/Graph/Graph.hpp"
using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';
signed main() {
int n, m;
cin >> n >> m;
auto graph = mtd::Graph(n);
for (int i = 0; i < m; ++i) {
int u, v, c;
cin >> u >> v >> c;
graph.addArc(u, v, c);
}
auto mf = mtd::Dinic(graph);
cout << mf.max_flow(0, n - 1) << endl;
}#line 1 "Test/Graph/Flow/Dinic.test.cpp"
#define PROBLEM \
"https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A"
#line 2 "Library/Graph/Flow/Dinic.hpp"
#include <list>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#line 2 "Library/Graph/Graph.hpp"
#include <deque>
#include <iostream>
#include <ranges>
#include <tuple>
#line 7 "Library/Graph/Graph.hpp"
namespace mtd {
template <class Node = long long, class Cost = long long>
class Graph {
using Edge = std::pair<Node, Cost>;
using Edges = std::vector<Edge>;
const int m_n;
std::vector<Edges> m_graph;
public:
Graph(int n) : m_n(n), m_graph(n) {}
Graph(const std::vector<Edges>& edges)
: m_n(edges.size()), m_graph(edges) {}
Graph(int n, const std::vector<std::tuple<Node, Node>>& edges,
bool is_arc = false, bool is_index1 = true)
: Graph<Node, Cost>(n) {
for (auto [u, v] : edges) {
u -= is_index1;
v -= is_index1;
if (is_arc) {
addArc(u, v);
} else {
addEdge(u, v);
}
}
}
Graph(int n, const std::vector<std::tuple<Node, Node, Cost>>& edges,
bool is_arc = false, bool is_index1 = true)
: Graph<Node, Cost>(n) {
for (auto [u, v, c] : edges) {
u -= is_index1;
v -= is_index1;
if (is_arc) {
addArc(u, v, c);
} else {
addEdge(u, v, c);
}
}
}
auto addEdge(const Node& f, const Node& t, const Cost& c = 1) {
addArc(f, t, c);
addArc(t, f, c);
}
auto addArc(const Node& f, const Node& t, const Cost& c = 1) {
m_graph[f].emplace_back(t, c);
}
auto getEdges(const Node& from) const {
class EdgesRange {
const typename Edges::const_iterator b, e;
public:
EdgesRange(const Edges& edges) : b(edges.begin()), e(edges.end()) {}
auto begin() const { return b; }
auto end() const { return e; }
};
return EdgesRange(m_graph[from]);
}
auto getEdges() const {
std::deque<std::tuple<Node, Node, Cost>> edges;
for (Node from : std::views::iota(0, m_n)) {
for (const auto& [to, c] : getEdges(from)) {
edges.emplace_back(from, to, c);
}
}
return edges;
}
auto getEdgesExcludeCost() const {
std::deque<std::pair<Node, Node>> edges;
for (Node from : std::views::iota(0, m_n)) {
for (const auto& [to, _] : getEdges(from)) {
edges.emplace_back(from, to);
}
}
return edges;
}
auto reverse() const {
auto rev = Graph<Node, Cost>(m_n);
for (const auto& [from, to, c] : getEdges()) { rev.addArc(to, from, c); }
return rev;
}
auto size() const { return m_n; };
auto debug(bool directed = false) const {
for (const auto& [f, t, c] : getEdges()) {
if (f < t || directed) {
std::cout << f << " -> " << t << ": " << c << std::endl;
}
}
}
};
} // namespace mtd
#line 11 "Library/Graph/Flow/Dinic.hpp"
namespace mtd {
template <class Node, class Cost>
class Dinic {
// using Node = int;
// using Cost = int;
struct HashPair {
template <class T1, class T2>
size_t operator()(const std::pair<T1, T2>& p) const {
auto hash1 = std::hash<T1>{}(p.first);
auto hash2 = std::hash<T2>{}(p.second);
size_t seed = 0;
seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
using PairGraph = std::unordered_map<std::pair<Node, Node>, Cost, HashPair>;
const Node m_n;
const PairGraph m_graph;
const std::vector<std::unordered_set<Node>> m_to_list;
static auto construct_to_list(const Graph<Node, Cost>& graph) {
std::vector<std::unordered_set<Node>> to_list(graph.size());
for (const auto& [f, t, c] : graph.getEdges()) {
to_list[f].emplace(t);
to_list[t].emplace(f);
}
return to_list;
}
static auto construct_graph(const Graph<Node, Cost>& graph) {
PairGraph pair_graph;
for (const auto& [f, t, c] : graph.getEdges()) {
pair_graph[std::pair<Node, Node>{f, t}] += c;
}
return pair_graph;
}
auto get_depth(Node s, const PairGraph& graph) const {
std::vector<Node> depth(m_n, -1);
std::queue<Node> q;
q.emplace(s);
depth[s] = 0;
while (!q.empty()) {
auto from = q.front();
q.pop();
for (const auto& to : m_to_list[from]) {
if (graph.find({from, to}) == graph.end()) { continue; }
if (depth[to] > -1) { continue; }
depth[to] = depth[from] + 1;
q.emplace(to);
}
}
return depth;
}
auto update_residual(Node s, PairGraph& residual,
const std::list<Node>& route) const {
Cost mn = 1e18;
auto from = s;
for (const auto& to : route)
if (from != to) {
mn = std::min(mn, residual[{from, to}]);
from = to;
}
from = s;
for (const auto& to : route)
if (from != to) {
auto& ft = residual[{from, to}];
ft -= mn;
if (ft == 0) { residual.erase({from, to}); }
residual[{to, from}] += mn;
from = to;
}
}
auto construct_residual(Node s, Node t) const {
auto residual = m_graph;
while (true) {
// BFS
auto depth = get_depth(s, residual);
// DFS
bool run = false;
std::vector<Node> visited(m_n);
auto f = [&](auto&& self, Node now, std::list<Node>& route) -> void {
route.emplace_back(now);
// tに到達していれば流す
if (now == t) {
update_residual(s, residual, route);
run = true;
}
for (const auto& to : m_to_list[now]) {
if (residual.find({now, to}) == residual.end()) { continue; }
if (depth[to] <= depth[now]) { continue; }
if (visited[to]) { continue; }
visited[to] = true;
;
self(self, to, route);
}
route.pop_back();
};
std::list<Node> route;
visited[s] = true;
f(f, s, route);
if (!run) { break; }
}
return residual;
}
public:
Dinic(const Graph<Node, Cost>& graph)
: m_n(graph.size()),
m_graph(construct_graph(graph)),
m_to_list(construct_to_list(graph)) {}
auto max_flow(Node s, Node t) const {
auto residual = construct_residual(s, t);
Cost val = 0;
for (const auto& to : m_to_list[s]) {
if (m_graph.find({s, to}) == m_graph.end()) { continue; }
val += m_graph.at({s, to}) - residual[{s, to}];
}
return val;
}
auto get_cut_list(Node s, Node t) const {
// 残余グラフで始点から到達できる集合
std::unordered_set<Node> st;
auto residual = construct_residual(s, t);
std::queue<Node> q;
auto add = [&](Node to) {
if (st.find(to) != st.end()) { return; }
q.emplace(to);
st.emplace(to);
};
add(s);
std::deque<Node> ans;
while (!q.empty()) {
auto from = q.front();
q.pop();
for (const auto& to : m_to_list[from]) {
if (residual.find({from, to}) == residual.end()) { continue; }
add(to);
}
}
std::deque<std::pair<Node, Node>> cut;
for (const auto& from : st)
for (const auto& to : m_to_list[from]) {
if (st.find(to) == st.end() &&
m_graph.find({from, to}) != m_graph.end()) {
cut.emplace_back(from, to);
}
}
return cut;
}
auto get_edge(Node s, Node t) const {
auto residual = construct_residual(s, t);
auto edge = Graph<Node, Cost>(m_n);
for (Node from = 0; from < m_n; ++from) {
for (const auto& to : m_to_list[from]) {
if (m_graph.find({from, to}) == m_graph.end()) { continue; }
auto val = m_graph.at({from, to}) - residual[{from, to}];
if (val > 0) { edge.addEdge(from, to, val); }
}
}
return edge;
}
};
} // namespace mtd
#line 5 "Test/Graph/Flow/Dinic.test.cpp"
#line 7 "Test/Graph/Flow/Dinic.test.cpp"
#line 9 "Test/Graph/Flow/Dinic.test.cpp"
using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';
signed main() {
int n, m;
cin >> n >> m;
auto graph = mtd::Graph(n);
for (int i = 0; i < m; ++i) {
int u, v, c;
cin >> u >> v >> c;
graph.addArc(u, v, c);
}
auto mf = mtd::Dinic(graph);
cout << mf.max_flow(0, n - 1) << endl;
}