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; }