mcf_graph

template <class Cap, class Cost>
struct mcf_graph;

概要

最小費用流

非負コストの有向辺からなるグラフに対し、最小費用流と流量・最小費用の折れ線を計算する。

名前	説明
`Cap`	容量の型
`Cost`	コストの型

名前	説明	計算量
`(constructor)`	(1) 頂点数を指定せずデフォルト構築する (2) n頂点0辺のグラフを構築する	$O(1)$

名前	説明	計算量
`size`	頂点数を返す	$O(1)$
`add_edge`	容量と単位流量あたりのコストを持つ有向辺を追加する	償却 $O(1)$
`get_edge`	指定した辺の現在状態を返す	$O(1)$
`edges`	全辺の現在状態を追加順で返す	追加した辺数を $m$ として $O(m)$
`flow`	(1) sからtへ流せるだけ流し、流量と最小費用を返す (2) sからtへ上限まで流し、流量と最小費用を返す	(1) 流量を $F$、頂点数を $n$、辺数を $m$ として $O(F(n+m)\log(n+m))$ (2) 実際の流量を $F$、頂点数を $n$、辺数を $m$ として $O(F(n+m)\log(n+m))$
`slope`	(1) 流量と最小費用の関係を表す折れ線を返す (2) 流量上限までの流量と最小費用の関係を表す折れ線を返す	(1) 最大流量を $F$、頂点数を $n$、辺数を $m$ として $O(F(n+m)\log(n+m))$ (2) 実際の流量を $F$、頂点数を $n$、辺数を $m$ として $O(F(n+m)\log(n+m))$

名前	説明	計算量
`edge`	追加した辺の現在状態	構築・各フィールドへのアクセスは $O(1)$

// (1)
mcf_graph();

// (2)
explicit mcf_graph(int n);

(1) 頂点数を指定せずデフォルト構築する

頂点数は未設定である。各演算を呼ぶ前に mcf_graph(n) で構築した値を代入する。

(2) n頂点0辺のグラフを構築する

int size() const;

頂点数を返す

int add_edge(int from, int to, Cap cap, Cost cost);

容量と単位流量あたりのコストを持つ有向辺を追加する

edge get_edge(int i);

指定した辺の現在状態を返す

std::vector<edge> edges();

全辺の現在状態を追加順で返す

// (1)
std::pair<Cap, Cost> flow(int s, int t);

// (2)
std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit);

(1) sからtへ流せるだけ流し、流量と最小費用を返す

(2) sからtへ上限まで流し、流量と最小費用を返す

// (1)
std::vector<std::pair<Cap, Cost>> slope(int s, int t);

// (2)
std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit);

(1) 流量と最小費用の関係を表す折れ線を返す

最初の要素は $(0,0)$。連続する3点が同一直線上にならないよう圧縮される。最後の要素は最大流量とその最小費用である。

(2) 流量上限までの流量と最小費用の関係を表す折れ線を返す

最初の要素は $(0,0)$。連続する3点が同一直線上にならないよう圧縮される。最後の要素は最大流量とflow_limitの小さい方に対する最小費用である。

struct edge;

追加した辺の現在状態

from、to、容量 cap、現在の流量 flow、単位流量あたりのコスト cost を保持する。