MaxFlow

It solves maximum flow problem.

Constructor

mf_graph<Cap> graph(int n)

It creates a graph of n vertices and 00 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 00. It returns an integer kk such that this is the kk-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 mm is the number of added edges.

min_cut

vector<bool> graph.min_cut(int s)

It returns a vector of length nn, such that the ii-th element is true if and only if there is a directed path from ss to ii in the residual network. The returned vector corresponds to a sts-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 ii-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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX