CFR 62 E. World Evil ( Flow, Mincut, DP, bitmask )

Problem - 62E - Codeforces

題意：
給一個多角形柱體形成的網路，問最大流是多少。
起點是上面的面的所有點，匯點是下面的面的所有點。

制約：
2 ≤ N ≤ 5
2 ≤ M ≤ 1e5

解法：
顯然不能暴力跑網路流算法。
考慮用 dp 求解。
最大流不好求，求最小割。
考慮水平的邊，一行是一定要割至少一個邊的。
考慮 dp[ i ][ s ]：做完前 i 列的決策後，s 代表目前這列是否可由左邊到達，此時最小花費。
轉移需要考慮這列的每個垂直的邊，對於其端點若且唯若恰有一個是可到達的，要將這個垂直的邊刪除掉。
答案是 dp[ M ][ ( 1 << N ) - 1 ]。
這麼做的正確性在於：
1. 狀態的定義和所求的關聯是顯然正確的。
2. 當轉移沒有發生的時候，顯然是不必要發生; 反之必要發生 ( 否則吃虧 )。
3. 轉移只需要知道所定義的狀態。

複雜度：
O( MAXM * MAXN * 2^MAXN )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5;
const int MAXM = int( 1e5 );

int N, M;
int Migi[ MAXM ][ MAXN ];
int Sita[ MAXM ][ MAXN ];

long long dp[ 1 << MAXN ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 1; i < M; ++i ) {
    for( int j = 0; j < N; ++j ) {
      cin >> Migi[ i ][ j ];
    }
  }
  for( int i = 0; i < M; ++i ) {
    for( int j = 0; j < N; ++j ) {
      cin >> Sita[ i ][ j ];
    }
  }
  memset( dp, 0x3f, sizeof( dp ) );
  dp[ 0 ] = 0;
  for( int i = 1; i < M; ++i ) {
    for( int j = 0; j < 1 << N; ++j ) {
      for( int k = 0; k < N; ++k ) if( ~j >> k & 1 ) {
        dp[ j | 1 << k ] = min( dp[ j | 1 << k ], dp[ j ] + Migi[ i ][ k ] );
      }
      for( int k = 0; k < N; ++k ) if( j >> k & 1 ^ j >> ( k + 1 ) % N & 1 ) {
        dp[ j ] += Sita[ i ][ k ];
      }
    }
  }
  cout << dp[ ( 1 << N ) - 1 ] << endl;
  return 0;
}