CFR 546 E. Soldier and Traveling ( Flow )
題意:
有 N 個城市,M 條無向邊。
起初第 i 個城市有 A[ i ] 個士兵。
現在進行一次移動,每個士兵都可以選擇不動,或者移動到相鄰的城市。
輸出方案,使得移動後第 i 個城市有 B[ i ] 個士兵。若不存在方案,輸出 -1。
制約:
1 ≤ N ≤ 100
0 ≤ M ≤ 200
0 ≤ A[ i ], B[ i ] ≤ 100
解法:
移動前的城市作為左邊一排的節點,移動後的作為右邊一排的節點。
源點至移動前的城市 i 建容量為 A[ i ] 的弧,移動後的城市 i 對匯點建容量為 B[ i ] 的弧。
對每對相鄰的 ( u, v ),從移動前的城市 u 建容量為無限大的弧至移動後的城市 v。
至於復原,看看殘餘流量剩多少就知道了。
複雜度:
O( O( Dinic's ) )
#include <bits/stdc++.h> using namespace std; template< class T > struct Dinic { static const int MAXV = 10000; static const T INF = 0x3f3f3f3f; struct Edge { int v; T f; int re; Edge( int _v, T _f, int _re ): v( _v ), f( _f ), re( _re ) {} }; int n, s, t, level[ MAXV ]; vector< Edge > E[ MAXV ]; int now[ MAXV ]; Dinic( int _n, int _s, int _t ): n( _n ), s( _s ), t( _t ) {} void add_edge( int u, int v, T f, bool bidirectional = false ) { E[ u ].emplace_back( v, f, E[ v ].size() ); E[ v ].emplace_back( u, 0, E[ u ].size() - 1 ); if( bidirectional ) { E[ v ].emplace_back( u, f, E[ u ].size() - 1 ); } } bool BFS() { memset( level, -1, sizeof( level ) ); queue< int > que; que.emplace( s ); level[ s ] = 0; while( not que.empty() ) { int u = que.front(); que.pop(); for( auto it: E[ u ] ) { if( it.f > 0 and level[ it.v ] == -1 ) { level[ it.v ] = level[ u ] + 1; que.emplace( it.v ); } } } return level[ t ] != -1; } T DFS( int u, T nf ) { if( u == t ) return nf; T res = 0; while( now[ u ] < E[ u ].size() ) { Edge &it = E[ u ][ now[ u ] ]; if( it.f > 0 and level[ it.v ] == level[ u ] + 1 ) { T tf = DFS( it.v, min( nf, it.f ) ); res += tf; nf -= tf; it.f -= tf; E[ it.v ][ it.re ].f += tf; if( nf == 0 ) return res; } else ++now[ u ]; } if( not res ) level[ u ] = -1; return res; } T flow( T res = 0 ) { while( BFS() ) { T temp; memset( now, 0, sizeof( now ) ); while( temp = DFS( s, INF ) ) { res += temp; res = min( res, INF ); } } return res; } }; const int MAXN = 100; int N, M; int A[ MAXN ]; int B[ MAXN ]; int ans[ MAXN ][ MAXN ]; signed main() { ios::sync_with_stdio( 0 ); cin >> N >> M; int SOURCE = N + N, SINK = N + N + 1; Dinic< int > din( SINK + 1, SOURCE, SINK ); int asum = 0, bsum = 0; for( int i = 0; i < N; ++i ) { cin >> A[ i ]; din.add_edge( SOURCE, i, A[ i ] ); din.add_edge( i, N + i, din.INF ); asum += A[ i ]; } for( int i = 0; i < N; ++i ) { cin >> B[ i ]; din.add_edge( N + i, SINK, B[ i ] ); bsum += B[ i ]; } if( asum != bsum ) cout << "NO\n", exit( 0 ); for( int i = 0; i < M; ++i ) { int u, v; cin >> u >> v; --u, --v; din.add_edge( u, N + v, din.INF ); din.add_edge( v, N + u, din.INF ); } if( din.flow() != asum ) cout << "NO\n", exit( 0 ); for( int i = 0; i < N; ++i ) { for( int j = 0; j < din.E[ i ].size(); ++j ) { int v = din.E[ i ][ j ].v - N; if( not ( v < N ) ) continue; ans[ i ][ v ] = din.INF - din.E[ i ][ j ].f; } } cout << "YES\n"; for( int i = 0; i < N; ++i ) { for( int j = 0; j < N; ++j ) { cout << ans[ i ][ j ] << " \n"[ j + 1 == N ]; } } return 0; }