PKU 2531 Network Saboteur

http://poj.org/problem?id=2531
n(<=20)この頂点をもつ完全グラフが与えられる。
ここでノードi,j間のコストをCijとするときに、グラフを２つの頂点集合A,Bに分割し
��Cij (i∈A,j∈B)を最大化しろというような問題

全探索。
愚直すぎると通らないようなので、少しだけ高速化しました。
差分計算とかまで考えなくて済んだので、よかったです。

int in[20][20];
int ans;
int n;
int g1[20],g2[20];
int g1s,g2s;

void dfs(int v){
  if(v==n){
    int tans=0;
    rep(i,g1s)rep(j,g2s)
      tans+=in[g1[i]][g2[j]];
    ans=max(ans,tans);
    return;
  }
  g1[g1s++]=v;
  dfs(v+1);
  g1s--;
  g2[g2s++]=v;
  dfs(v+1);
  g2s--;
}

main(){
  cin>>n;
  rep(i,n)rep(j,n)scanf("%d",in[i]+j);
  dfs(0);
  cout<<ans<<endl;
}