最小費用 $\boldsymbol{b}$-フロー (minimum cost $\boldsymbol{b}$-flow) 最短路反復法 (successive shortest path algorithm) 版
(include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_b-flow.hpp)
最小費用流 (minimum cost flow)
計算量
最大流の流量を $F$ とおく。
計算量
最小費用 $s$-$t$-フロー 最短路反復法版
$O(\lvert V \rvert \lvert E \rvert + F \lvert E \rvert \log{\lvert V \rvert})$
最小費用 $\boldsymbol{b}$-フロー 最短路反復法版
コスト負の辺の容量の総和を $F^{\prime}$ とおくと $O((F + F^{\prime})\lvert E \rvert \log{\lvert V \rvert})$。
仕様
最小費用 $s$-$t$-フロー 最短路反復法版
template < typename T , typename U >
struct MinimumCostSTFlow ;
メンバ変数
名前
説明
const U uinf
$\infty$
std::vector<std::vector<Edge>> graph
残余グラフ
メンバ関数
名前
効果・戻り値
備考
explicit MinimumCostSTFlow(const int n, const U uinf = std::numeric_limits<U>::max());
頂点数 $N$ のオブジェクトを構築する。
void add_edge(const int src, const int dst, const T cap, const U cost);
始点 $\mathrm{src}$、終点 $\mathrm{dst}$、容量 $\mathrm{cap}$、コスト $\mathrm{cost}$ の辺を加える。
U solve(const int s, const int t, T flow);
始点 $s$ から終点 $t$ まで流量 $\mathrm{flow}$ のフローを流すときの最小コスト。ただし流せないときは uinf
を返す。
U solve(const int s, const int t);
始点 $s$ から終点 $t$ まで流量任意のフローを流すときの最小コスト
流量は $\mathrm{tinf} - \mathrm{flow}$ である。
std::pair<T, U> minimum_cost_maximum_flow(const int s, const int t, const T flow);
始点 $s$ から終点 $t$ まで流量 $\mathrm{flow}$ 以下のフローを流すときの最小費用最大流。最大流と最小費用の組を返す。
メンバ型
メンバ変数
名前
説明
int dst
終点
int rev
頂点 $\mathrm{dst}$ における逆辺のインデックス
T cap
残りの容量
U cost
流量 $1$ のフローを流すときのコスト
メンバ関数
名前
効果
explicit Edge(const int dst, const T cap, const U cost, const int rev);
コンストラクタ
最小費用 $\boldsymbol{b}$-フロー 最短路反復法版
template < typename T , typename U >
struct MinimumCostBFlow ;
メンバ変数
名前
説明
const U uinf
$\infty$
std::vector<std::vector<Edge>> graph
残余グラフ
メンバ関数
名前
効果・戻り値
explicit MinimumCostBFlow(const int n, const U uinf = std::numeric_limits<U>::max());
頂点数 $N$ のオブジェクトを構築する。
void add_edge(int src, int dst, const T cap, U cost);
始点 $\mathrm{src}$、終点 $\mathrm{dst}$、容量 $\mathrm{cap}$、コスト $\mathrm{cost}$ の辺を加える。
void supply_or_demand(const int ver, const T amount);
$b_{\mathrm{ver}} \gets b_{\mathrm{ver}} + \mathrm{amount}$
U solve();
最小費用循環流。ただし流せないときは uinf
を返す。
U solve(const int s, const int t, const T flow);
始点 $s$ から終点 $t$ まで流量 $\mathrm{flow}$ のフローを流すときの最小コスト。ただし流せないときは uinf
を返す。
メンバ型
メンバ変数
名前
説明
int dst
終点
int rev
頂点 $\mathrm{dst}$ における逆辺のインデックス
T cap
残りの容量
U cost
流量 $1$ のフローを流すときのコスト
メンバ関数
名前
効果
explicit Edge(const int dst, const T cap, const U cost, const int rev);
コンストラクタ
注意
流量正の辺の合計コストの和を最小化する問題を最小費用流で解くことはできない。
参考文献
秋葉拓哉,岩田陽一,北川宜稔:プログラミングコンテストチャレンジブック [第2版],pp.199-205,マイナビ出版(2012)
最小費用 $s$-$t$-フロー 最短路反復法版
Jack Edmonds, Richard M. Karp: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM , Vol. 19, No. 2, pp. 248–264 (1972). https://doi.org/10.1145/321694.321699
http://sigma425.hatenablog.com/entry/2014/10/12/122018
最小費用 $\boldsymbol{b}$-フロー 最短路反復法版
https://snuke.hatenablog.com/entry/2017/06/07/115821
TODO
容量スケーリング
https://misawa.github.io/others/flow/lets_use_capacity_scaling.html
最小費用 $\boldsymbol{b}$-フロー
https://misawa.github.io/others/flow/library_design.html
https://twitter.com/Mi_Sawa/status/1283768916775321601
https://noshi91.hatenablog.com/entry/2021/12/15/012019
https://judge.yosupo.jp/problem/min_cost_b_flow
グラフにコスト負の閉路が存在するとき
Submissons
Verified with
Code
#ifndef EMTHRM_GRAPH_FLOW_MINIMUM_COST_FLOW_MINIMUM_COST_B_FLOW_HPP_
#define EMTHRM_GRAPH_FLOW_MINIMUM_COST_FLOW_MINIMUM_COST_B_FLOW_HPP_
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
namespace emthrm {
template < typename T , typename U >
struct MinimumCostBFlow {
struct Edge {
int dst , rev ;
T cap ;
U cost ;
explicit Edge ( const int dst , const T cap , const U cost , const int rev )
: dst ( dst ), rev ( rev ), cap ( cap ), cost ( cost ) {}
};
const U uinf ;
std :: vector < std :: vector < Edge >> graph ;
explicit MinimumCostBFlow ( const int n ,
const U uinf = std :: numeric_limits < U >:: max ())
: uinf ( uinf ), graph ( n + 2 ), n ( n ), res ( 0 ), b ( n + 2 , 0 ) {}
void add_edge ( int src , int dst , const T cap , U cost ) {
if ( cost < 0 ) {
b [ src ] -= cap ;
b [ dst ] += cap ;
res += cost * cap ;
std :: swap ( src , dst );
cost = - cost ;
}
graph [ src ]. emplace_back ( dst , cap , cost , graph [ dst ]. size ());
graph [ dst ]. emplace_back ( src , 0 , - cost , graph [ src ]. size () - 1 );
}
void supply_or_demand ( const int ver , const T amount ) { b [ ver ] += amount ; }
U solve () {
assert ( std :: reduce ( b . begin (), b . end (), static_cast < T > ( 0 )) == 0 );
T flow = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
if ( b [ i ] > 0 ) {
add_edge ( n , i , b [ i ], 0 );
flow += b [ i ];
} else if ( b [ i ] < 0 ) {
add_edge ( i , n + 1 , - b [ i ], 0 );
}
}
std :: vector < int > prev_v ( n + 2 , - 1 ), prev_e ( n + 2 , - 1 );
std :: vector < U > dist ( n + 2 ), potential ( n + 2 , 0 );
std :: priority_queue < std :: pair < U , int > , std :: vector < std :: pair < U , int >> ,
std :: greater < std :: pair < U , int >>> que ;
while ( flow > 0 ) {
std :: fill ( dist . begin (), dist . end (), uinf );
dist [ n ] = 0 ;
que . emplace ( 0 , n );
while ( ! que . empty ()) {
const auto [ d , ver ] = que . top ();
que . pop ();
if ( d > dist [ ver ]) continue ;
for ( int i = 0 ; std :: cmp_less ( i , graph [ ver ]. size ()); ++ i ) {
const Edge & e = graph [ ver ][ i ];
const U nxt = dist [ ver ] + e . cost + potential [ ver ] - potential [ e . dst ];
if ( e . cap > 0 && dist [ e . dst ] > nxt ) {
dist [ e . dst ] = nxt ;
prev_v [ e . dst ] = ver ;
prev_e [ e . dst ] = i ;
que . emplace ( dist [ e . dst ], e . dst );
}
}
}
if ( dist [ n + 1 ] == uinf ) return uinf ;
for ( int i = 0 ; i < n + 2 ; ++ i ) {
if ( dist [ i ] != uinf ) potential [ i ] += dist [ i ];
}
T f = flow ;
for ( int v = n + 1 ; v != n ; v = prev_v [ v ]) {
f = std :: min ( f , graph [ prev_v [ v ]][ prev_e [ v ]]. cap );
}
flow -= f ;
res += potential [ n + 1 ] * f ;
for ( int v = n + 1 ; v != n ; v = prev_v [ v ]) {
Edge & e = graph [ prev_v [ v ]][ prev_e [ v ]];
e . cap -= f ;
graph [ v ][ e . rev ]. cap += f ;
}
}
return res ;
}
U solve ( const int s , const int t , const T flow ) {
supply_or_demand ( s , flow );
supply_or_demand ( t , - flow );
return solve ();
}
private:
int n ;
U res ;
std :: vector < T > b ;
};
} // namespace emthrm
#endif // EMTHRM_GRAPH_FLOW_MINIMUM_COST_FLOW_MINIMUM_COST_B_FLOW_HPP_
#line 1 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_b-flow.hpp"
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
namespace emthrm {
template < typename T , typename U >
struct MinimumCostBFlow {
struct Edge {
int dst , rev ;
T cap ;
U cost ;
explicit Edge ( const int dst , const T cap , const U cost , const int rev )
: dst ( dst ), rev ( rev ), cap ( cap ), cost ( cost ) {}
};
const U uinf ;
std :: vector < std :: vector < Edge >> graph ;
explicit MinimumCostBFlow ( const int n ,
const U uinf = std :: numeric_limits < U >:: max ())
: uinf ( uinf ), graph ( n + 2 ), n ( n ), res ( 0 ), b ( n + 2 , 0 ) {}
void add_edge ( int src , int dst , const T cap , U cost ) {
if ( cost < 0 ) {
b [ src ] -= cap ;
b [ dst ] += cap ;
res += cost * cap ;
std :: swap ( src , dst );
cost = - cost ;
}
graph [ src ]. emplace_back ( dst , cap , cost , graph [ dst ]. size ());
graph [ dst ]. emplace_back ( src , 0 , - cost , graph [ src ]. size () - 1 );
}
void supply_or_demand ( const int ver , const T amount ) { b [ ver ] += amount ; }
U solve () {
assert ( std :: reduce ( b . begin (), b . end (), static_cast < T > ( 0 )) == 0 );
T flow = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
if ( b [ i ] > 0 ) {
add_edge ( n , i , b [ i ], 0 );
flow += b [ i ];
} else if ( b [ i ] < 0 ) {
add_edge ( i , n + 1 , - b [ i ], 0 );
}
}
std :: vector < int > prev_v ( n + 2 , - 1 ), prev_e ( n + 2 , - 1 );
std :: vector < U > dist ( n + 2 ), potential ( n + 2 , 0 );
std :: priority_queue < std :: pair < U , int > , std :: vector < std :: pair < U , int >> ,
std :: greater < std :: pair < U , int >>> que ;
while ( flow > 0 ) {
std :: fill ( dist . begin (), dist . end (), uinf );
dist [ n ] = 0 ;
que . emplace ( 0 , n );
while ( ! que . empty ()) {
const auto [ d , ver ] = que . top ();
que . pop ();
if ( d > dist [ ver ]) continue ;
for ( int i = 0 ; std :: cmp_less ( i , graph [ ver ]. size ()); ++ i ) {
const Edge & e = graph [ ver ][ i ];
const U nxt = dist [ ver ] + e . cost + potential [ ver ] - potential [ e . dst ];
if ( e . cap > 0 && dist [ e . dst ] > nxt ) {
dist [ e . dst ] = nxt ;
prev_v [ e . dst ] = ver ;
prev_e [ e . dst ] = i ;
que . emplace ( dist [ e . dst ], e . dst );
}
}
}
if ( dist [ n + 1 ] == uinf ) return uinf ;
for ( int i = 0 ; i < n + 2 ; ++ i ) {
if ( dist [ i ] != uinf ) potential [ i ] += dist [ i ];
}
T f = flow ;
for ( int v = n + 1 ; v != n ; v = prev_v [ v ]) {
f = std :: min ( f , graph [ prev_v [ v ]][ prev_e [ v ]]. cap );
}
flow -= f ;
res += potential [ n + 1 ] * f ;
for ( int v = n + 1 ; v != n ; v = prev_v [ v ]) {
Edge & e = graph [ prev_v [ v ]][ prev_e [ v ]];
e . cap -= f ;
graph [ v ][ e . rev ]. cap += f ;
}
}
return res ;
}
U solve ( const int s , const int t , const T flow ) {
supply_or_demand ( s , flow );
supply_or_demand ( t , - flow );
return solve ();
}
private:
int n ;
U res ;
std :: vector < T > b ;
};
} // namespace emthrm
Back to top page