CFR 11 D. A Simple Task ( DP, Bitmask, Hamiltonian Walk )

Problem - 11D - Codeforces

題意：
給一個無向圖。問有多少個簡單環 ( 無重複經過的點的環 )。

資料規模：
N ≤ 19
TL: 2000 ms

解法：
考慮一個環，選定一個點 ( 這裡用編號最小的點 ) 切開之後變成一條鍊，假設原本是 abcd 這樣的環，那其實可以用點的集合和末端節點編號歸類描述。
dp[ s ][ i ] : 以 lowbit( s ) 為起點，拜訪 s 中每個節點恰好一次，最後在節點 i 的方法數

注意 lowbit 不能轉移。
最後枚舉所有鍊，若末端和 lowbit 有邊，就加到解裡。最後要除以二，原因是同一個環順時針接的跟逆時針接的都會被計入。

時間 / 空間複雜度：
O( N^2 * 2^N ) / O( N * 2^N )

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

typedef vector< int > vi;

const int MAXN = 19;

int N, M;
int adj[ MAXN ][ MAXN ];
long long dp[ 1 << MAXN ][ MAXN ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < M; ++i ){
    int u, v; cin >> u >> v; --u, --v;
    adj[ u ][ v ] = adj[ v ][ u ] = 1;
  }
  for( int i = 0; i < N; ++i ){
    dp[ 1 << i ][ i ] = 1;
  }
  for( int s = 0; s < 1 << N; ++s ){
    if( __builtin_popcount( s ) < 2 ) continue;
    int lobit = __builtin_ctz( s );
    for( int i = 0; i < N; ++i ){
      if( i == lobit ) continue;
      if( ~s >> i & 1 ) continue;
      for( int j = 0; j < N; ++j ){
        if( ~s >> j & 1 ) continue;
        if( not adj[ i ][ j ] ) continue;
        dp[ s ][ i ] += dp[ s ^ 1 << i ][ j ];
      }
    }
  }
  long long ans = 0;
  for( int s = 0; s < 1 << N; ++s ){
    if( __builtin_popcount( s ) < 3 ) continue;
    int lobit = __builtin_ctz( s );
    for( int i = 0; i < N; ++i ){
      if( i == lobit ) continue;
      if( not adj[ i ][ lobit ] ) continue;
      ans += dp[ s ][ i ];
    }
  }
  cout << ans / 2 << endl;
  return 0;
}