POJ 2531 深搜剪枝

题意：全局最大割。

分析：有相应的算法，数据量很小，可以枚举源点，汇点，最大流。

这里用DFS，状态定义：分成两个集合，刚开始S集合全部点，然后一个一个放，这是一个回溯的过程。

没剪枝也过了。

剪枝技巧：当前这个节点放到T集合，比之前还小，那么一定，这个点不在T集合里面。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int maxn = 20 + 5;
int n;
int a[maxn][maxn];
int dep[maxn];

int ans;


void dfs(int u,int m) {
    dep[u] = 1;
    int tmp = m;

    for(int i=0;i<n;i++) {
        if(dep[i]==0)
            m+=a[i][u];
        else m-=a[i][u];
    }

    if(m>ans)
        ans = m;

    for(int i=u+1;i<n;i++) {
        if(m > tmp) {
            dfs(i,m);
            dep[i] = 0;
        }
    }
}

int main()
{
    scanf("%d",&n);

    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            scanf("%d",&a[i][j]);
        }
    }

    memset(dep,0,sizeof(dep));

    ans = 0;
    dfs(0,0);
    printf("%d
",ans);

    return 0;
}