CFR 362 E. Petya and Pipes ( MCMF, Binary Search )
題意:
有 N 個節點,以及有向弧,用鄰接矩陣表示。
若 C[ i ][ j ] = 0,代表 ( i, j ) 之間沒有弧。
源點 1,匯點 N。
對於一個弧,可以花費一單位的金子增加一單位流量。
你有 K 單位的金子,問最大流量。
制約:
2 ≤ N ≤ 50
0 ≤ K ≤ 1000
0 ≤ C[ i ][ j ] ≤ 1e6
C[ i ][ i ] = 0
if C[ i ][ j ] = 0, then C[ j ][ i ] = 0
解法:
二分搜最大流量。
建圖時對所有既存的弧之上額外添一個弧,容量無限大,費用 1。
我們想知道在最大流量 x 的前提下,花費是否不超過 K。
那麼建一個超級源點連到源點,容量 x,費用 0。
複雜度:
O( N ** 2 * lg MAXC )
#include <bits/stdc++.h> using namespace std; template< class TF, class TC > struct CostFlow { static const int MAXV = 10000; static constexpr TC INF = 1e9; struct Edge { int v, r; TF f; TC c; Edge( int _v, int _r, TF _f, TC _c ): v( _v ), r( _r ), f( _f ), c( _c ) {} }; int n, s, t, pre[ MAXV ], pre_E[ MAXV ], inq[ MAXV ]; TF fl; TC dis[ MAXV ], cost; vector< Edge > E[ MAXV ]; CostFlow( int _n, int _s, int _t ): n( _n ), s( _s ), t( _t ), fl( 0 ), cost( 0 ) {} void add_edge( int u, int v, TF f, TC c ) { E[ u ].emplace_back( v, E[ v ].size(), f, c ); E[ v ].emplace_back( u, E[ u ].size() - 1, 0, -c ); } pair< TF, TC > flow() { while( true ) { for( int i = 0; i < n; ++i ) { dis[ i ] = INF; inq[ i ] = 0; } dis[ s ] = 0; queue< int > que; que.emplace( s ); while( not que.empty() ) { int u = que.front(); que.pop(); inq[ u ] = 0; for( int i = 0; i < E[ u ].size(); ++i ) { int v = E[ u ][ i ].v; TC w = E[ u ][ i ].c; if( E[ u ][ i ].f > 0 and dis[ v ] > dis[ u ] + w ) { pre[ v ] = u; pre_E[ v ] = i; dis[ v ] = dis[ u ] + w; if( not inq[ v ] ) { inq[ v ] = 1; que.emplace( v ); } } } } if( dis[ t ] == INF ) break; TF tf = INF; for( int v = t, u, l; v != s; v = u ) { u = pre[ v ]; l = pre_E[ v ]; tf = min( tf, E[ u ][ l ].f ); } for( int v = t, u, l; v != s; v = u ) { u = pre[ v ]; l = pre_E[ v ]; E[ u ][ l ].f -= tf; E[ v ][ E[ u ][ l ].r ].f += tf; } cost += tf * dis[ t ]; fl += tf; } return { fl, cost }; } }; const int MAXN = 50; int N, K; int C[ MAXN ][ MAXN ]; signed main() { ios::sync_with_stdio( 0 ); cin >> N >> K; for( int i = 0; i < N; ++i ) { for( int j = 0; j < N; ++j ) { cin >> C[ i ][ j ]; } } int lb = 0, ub = 1e9; while( lb + 1 != ub ) { int mid = lb + ub >> 1; CostFlow< int, long long > mcmf( N + 1, N, N - 1 ); mcmf.add_edge( N, 0, mid, 0 ); for( int i = 0; i < N; ++i ) { for( int j = 0; j < N; ++j ) if( C[ i ][ j ] ) { mcmf.add_edge( i, j, C[ i ][ j ], 0 ); mcmf.add_edge( i, j, mcmf.INF, 1 ); } } long long flow, cost; tie( flow, cost ) = mcmf.flow(); ( flow == mid and cost <= K ? lb : ub ) = mid; } cout << lb << endl; return 0; }