MaxFlow

It solves maximum flow problem.

Constructor

mf_graph<Cap> graph(int n)

It creates a graph of n vertices and $0$ edges. Cap is the type of the capacity.

Constraints

Complexity

add_edge

int graph.add_edge(int from, int to, Cap cap);

It adds an edge oriented from the vertex from to the vertex to with the capacity cap and the flow amount $0$. It returns an integer $k$ such that this is the $k$-th edge that is added.

Constraints

Complexity

flow

(1) Cap graph.flow(int s, int t);
(2) Cap graph.flow(int s, int t, Cap flow_limit);

Constraints

Complexity

where $m$ is the number of added edges.

min_cut

vector<bool> graph.min_cut(int s)

It returns a vector of length $n$, such that the $i$-th element is true if and only if there is a directed path from $s$ to $i$ in the residual network. The returned vector corresponds to a $s-t$ minimum cut after calling flow(s, t) exactly once without flow_limit. See Appendix for further details.

Complexity

get_edge / edges

struct mf_graph<Cap>::edge {
    int from, to;
    Cap cap, flow;
};

(1) mf_graph<Cap>::edge graph.get_edge(int i);
(2) vector<mf_graph<Cap>::edge> graph.edges();

Constraints

Complexity

change_edge

void graph.change_edge(int i, Cap new_cap, Cap new_flow);

It changes the capacity and the flow amount of the $i$-th edge to new_cap and new_flow, respectively. It doesn't change the capacity or the flow amount of other edges. See Appendix for further details.

Constraints

Complexity

Examples

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_d

#include <atcoder/maxflow> #include <iostream> using namespace std; using namespace atcoder; int main() { int n, m; cin >> n >> m; vector<string> grid(n); for (int i = 0; i < n; i++) { cin >> grid[i]; } /** * generate (s -> even grid -> odd grid -> t) graph * grid(i, j) correspond to vertex (i * m + j) **/ mf_graph<int> g(n * m + 2); int s = n * m, t = n * m + 1; // s -> even / odd -> t for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == '#') continue; int v = i * m + j; if ((i + j) % 2 == 0) { g.add_edge(s, v, 1); } else { g.add_edge(v, t, 1); } } } // even -> odd for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if ((i + j) % 2 || grid[i][j] == '#') continue; int v0 = i * m + j; if (i && grid[i - 1][j] == '.') { int v1 = (i - 1) * m + j; g.add_edge(v0, v1, 1); } if (j && grid[i][j - 1] == '.') { int v1 = i * m + (j - 1); g.add_edge(v0, v1, 1); } if (i + 1 < n && grid[i + 1][j] == '.') { int v1 = (i + 1) * m + j; g.add_edge(v0, v1, 1); } if (j + 1 < m && grid[i][j + 1] == '.') { int v1 = i * m + (j + 1); g.add_edge(v0, v1, 1); } } } cout << g.flow(s, t) << endl; auto edges = g.edges(); for (auto e : edges) { if (e.from == s || e.to == t || e.flow == 0) continue; int i0 = e.from / m, j0 = e.from % m; int i1 = e.to / m, j1 = e.to % m; if (i0 == i1 + 1) { grid[i1][j1] = 'v'; grid[i0][j0] = '^'; } else if (j0 == j1 + 1) { grid[i1][j1] = '>'; grid[i0][j0] = '<'; } else if (i0 == i1 - 1) { grid[i0][j0] = 'v'; grid[i1][j1] = '^'; } else { grid[i0][j0] = '>'; grid[i1][j1] = '<'; } } for (int i = 0; i < n; i++) { cout << grid[i] << endl; } return 0; }