好题分享-poj2531【Network Saboteur】

大意：给出一个n*n的举证，a[i][j]表示第i个点和第j个点的联系，所以a[i][j]=a[j][i]
现在要将n个物品分成俩个部分，要使得俩个部分之间点的联系和最大，要怎么分？
考虑dfs找所有状态，处理联系和最大的时候用到的方法比较巧妙

#include<iostream>
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<set>
#include<bitset>
#include<vector>
#define ll long long
#define ull unsigned long long
#define up_b upper_bound
#define low_b lower_bound
#define m_p make_pair
#define mem(a) memset(a,0,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define INF 0x3f3f3f3f
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const ll mod=1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
//inline ll Inverse(ll x) { return qpow(x,mod-2);}
//inline ll C(ll n,ll m) { return fact[n]*inv[m]%mod*inv[n-m]%mod;}
double round(double r){return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);}//四舍五入
const int maxn=1e5+5;
//const int dx[]={-1,0,1,0};
//const int dy[]={0,1,0,-1};
//ll fact[105];
//ll inv[105];
int n,dep[25],ans;
int a[25][25];
void dfs(int id,int data)
{
    dep[id]=1;
    int tmp=data;
    rep(i,1,n)
    {
        if(dep[i]==0) tmp+=a[i][id];//在集合0里面的话就加上俩点之间的联系 
        else tmp-=a[i][id]; //在集合1里面的话就减去，因为有可能在上一步第i个点在集合0之中，tmp加上了联系，现在第i个点到集合1里面了，要把联系剪断 
    }
    ans=max(ans,tmp);
    rep(i,id+1,n)
    {
        if(tmp>data)
        {
            dfs(i,tmp);
            dep[i]=0;//回溯时将这个点取消，即切换状态 
        }
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        ans=0;mem(dep);
        rep(i,1,n)
            rep(j,1,n)
                a[i][j]=read();
        dfs(1,0);
        printf("%d\n",ans);        
    }

}