MaxFlow

最大フロー問題 を解くライブラリです。

コンストラクタ

mf_graph<Cap> graph(int n)

n 頂点 $0$ 辺のグラフを作る。Capは容量の型。

制約

計算量

add_edge

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

fromからtoへ最大容量cap、流量 $0$ の辺を追加し、何番目に追加された辺かを返す。

制約

計算量

flow

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

制約

計算量

$m$ を追加された辺数として

min_cut

vector<bool> graph.min_cut(int s)

長さ $n$ のvectorを返す。$i$ 番目の要素には、頂点 $s$ から $i$ へ残余グラフで到達可能なとき、またその時のみ true を返す。flow(s, t)をflow_limitなしでちょうど一回呼んだ後に呼ぶと、返り値は $s$, $t$ 間のmincutに対応します。詳細な挙動は Appendix を参照してください。

計算量

$m$ を追加された辺数として

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();

制約

計算量

$m$ を追加された辺数として

change_edge

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

$i$ 番目に追加された辺の容量、流量をnew_cap, new_flowに変更する。他の辺の容量、流量は変更しない。詳細は Appendix を参照してください

制約

計算量

使用例

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; }