0w1

UVA 11506 - Angry Programmer ( Mincut, Flow )

UVa Online Judge

題意:
有若干個節點跟雙向連接的網路線連接結點之間。你可以破壞節點或者破壞網路線,希望 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;
}