UVA 11506 - Angry Programmer ( Mincut, Flow )
題意:
有若干個節點跟雙向連接的網路線連接結點之間。你可以破壞節點或者破壞網路線,希望 1 號節點連不上 M 號節點。給你破壞每個物件的花費,問需要的最小總花費多少。
制約:
2 ≤ 節點數( M ) ≤ 50, 0 ≤ 網路線數( W ) ≤ 1000
0 ≤ 容量 ≤ 1e5
解法:
最小割等於最大流,把節點拆成一進一出,建完圖就可以最大流了。
時間複雜度:
O( M**2 * W )
#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 ) { E[ u ].emplace_back( v, f, E[ v ].size() ); E[ v ].emplace_back( u, 0, int( E[ u ].size() ) - 1 ); // E[ v ].emplace_back( u, f, int( 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; } } return res; } }; signed main() { ios::sync_with_stdio( 0 ); int M, W; while( cin >> M >> W and M + W ) { Dinic< int > din( M * 2, 0, M + M - 1 ); din.add_edge( 0, M + 0, din.INF ); din.add_edge( M - 1, M + M - 1, din.INF ); for( int i = 2; i < M; ++i ) { int id, c; cin >> id >> c; --id; din.add_edge( id, M + id, c ); } for( int i = 0; i < W; ++i ) { int j, k; cin >> j >> k; --j, --k; int d; cin >> d; din.add_edge( M + j, k, d ); din.add_edge( M + k, j, d ); } cout << din.flow() << "\n"; } return 0; }