最小費用流 (PrimalDual)

Last updated：2018-03-22　10:47:40
Category:グラフ, Tag： 最小費用流

概要

各辺$e\in E$が$($フローを流せる最大容量$cap$,流すときにかかるコスト$cost)$を持つ有向グラフ$G=(V,E)$について，
頂点$s$から頂点$t$へ流量$f$を流すときの最小費用流を求める．

計算量

最短経路を求めるアルゴリズムとしてdijkstra法を使っており，
計算量は$O(f|E|\log|V|)$．

使い方

// 頂点数|V|=nの有向グラフGを用意
PrimalDual pd(n);

// Gに頂点uから頂点vに向かう辺(容量c, コストd)を追加
pd.addEdge(u, v, c, d);

// 頂点sから頂点t流量fの最小費用流を求める
int res = pd.minCostFlow(s, t, f);

実装例

問題例

参考文献