Poj 2531 Network Saboteur（DFS+剪枝）

2531 -- Network Saboteur (poj.org)

#include<iostream>
#include<cstring>
using namespace std;
const int N=30;
int C[N][N],n,ans;
bool group[N];
void DFS(int num,int sum){
    group[num]=true;
    int tmp=sum;
    for(int i=1;i<=n;i++){
        if(group[i]) tmp-=C[num][i];
        else tmp+=C[num][i];
    }
    ans=max(ans,tmp);
    if(tmp>sum){
        for(int i=num+1;i<=n;i++){
            DFS(i,tmp);
        }
    }
    group[num]=false;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>C[i][j];
    memset(group,0,sizeof(group));
    ans=0;
    DFS(1,0);
    cout<<ans<<endl;
    
    return 0;
}