2531 Network Saboteur

http://poj.org/problem?id=2531

ほうしん

グラフの最大カットを求める。
最大カットを求める問題は、NP完全問題らしい
状態数2^20を全探索した

ソース

#include<iostream>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

int adj[20][20] = {};

inline int lex_next(int x) {
  int t = (x|(x-1)) + 1;
  return t | ((((t & -t) / (x & -x)) >> 1) - 1);
}

int main() {
  int n,i,j,k,l;
  cin>>n;
  rep(i,n) rep(j,n) cin>>adj[i][j];

  int ans = 0,t;
  REP(l,1,n/2+1) {
    for(i=(1<<l)-1; i<(1<<n); i = lex_next(i)) {
      t = 0;
      rep(j,n) if(i&(1<<j)) rep(k,n) if(!(i&(1<<k))) t += adj[j][k];
      ans = max(ans,t);
    }
  }
  cout<<ans<<endl;
}