POJ 2531 Network Saboteur(DFS+枝切り)

タイトルリンク:http://poj.org/problem?id=2531
n個の点があって、任意の2点の間の重み値を与えて、今点をそれぞれA集合あるいはB集合に入れて、2つの集合の重み値の和の最大値を求めます.
直接暴力は過去にも問題なく、110 ms、47 msまで枝を切った.
最初はすべての集合がAにあると考えられ,次に列挙して点をBに加える.
具体的な説明はコードを参照してください.

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<cmath>
using namespace std;

const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int maxn=25;
int n,c[maxn][maxn];
int set[maxn];
int ans;

void dfs(int id,int sum){
	set[id]=1;// id  B  
	int tmp=sum;
	for(int i=1;i<=n;i++){
		if(set[i]==0) tmp+=c[i][id];//   id         
		else tmp-=c[i][id];//       id        
	}
	if(tmp>ans) ans=tmp;
	for(int i=id+1;i<=n;i++){
		if(tmp>sum){//  ，          ，          
			dfs(i,tmp);
			set[i]=0;
		}
	}
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif
    while(~scanf("%d",&n)){
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    			scanf("%d",&c[i][j]);
    	memset(set,0,sizeof(set));//        A  
    	ans=0;
    	dfs(1,0);//          
    	printf("%d
",ans);
    }
	return 0;
}