首先我们可以想到情况是对称的，也就是说枚举所有的分类情况中，有一半是冗余的。
举个例子来说，有5个节点，1、2、3分配为A组，4、5分配给B组，这个分类的策略所计算的结果和1、2、3分配为B组，4、5分配给A组是一样的。那么怎么去除这一半的冗余呢，其实很简单，我们强制第1个节点分配给A组，那么后面不管怎么分，全体情况都不会有重复的了。

但是情况还是太多，20个节点有2^19中分类情况，我的剪枝方法是这样的：

给n个节点，它能达到的流量上限是多少？我们知道将n个节点分为两个部分，每个部分不为空，那么对于一个部分来说，内部节点直接的边是完全没用，需要去掉的。当我们把n个节点等分时（也就是A组n/2个节点，B组n/2个节点），去掉的边最少（同学们可以用代数方法表示下，可以发现是个二次函数，n/2是最低点），大约为m = n^2/4 - n/2（n为偶数情况）。既然我们n个节点进行分组至少要去掉这么多边，那么我们将边的总和去掉边权值最少的m条边，就是一个流量的最高上限。

通过上面的方法我们可以很快的在DFS中估计出当前策略向下枚举的最高流量极限，这样就可以剪枝了。根据我的试验，这个剪枝方法非常管用，在n=20的情况下，枚举到树的叶子节点的情况基本没有超过10的，很给力。

附上我的0MS代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int c[20][20];
int n;
bool v[20];
int maxTraffic;
// remain[i]代表 i~n-1的节点能产生的极限最大traffic 
int remain[30];  
int num=0;

int calc(){
    int res = 0;
    for( int i=0; i<n; ++i ){
        for( int j=i+1; j<n; ++j ){
                if( v[i] ^ v[j] )  //v[i] != v[j]
                    res += c[i][j];
        }
    }
    return res;
}

int calcPartial( int idx, int partial ){
    int res = partial;
    for( int i=0; i<idx; ++i ){
        if( v[i] ^ v[idx] )
            res += c[i][idx];
    }
    return res;
}

int calcOpt( int idx, int partial ){
    int t = partial;
    int a,b;
    for( int i=idx + 1; i<n; ++i ){
        a=b=0;
        for( int j=0; j<=idx; ++j ){
            if( v[j] )
                a += c[i][j];
            else
                b += c[i][j];
        }
        t += max( a, b );
    }
    t += remain[idx+1];
    return min( remain[0], t );
}

void dfs( int idx, int partial ){
    if( idx == n ){
        maxTraffic = max( maxTraffic, partial );
        ++num;
        return;
    }
    v[idx] = true;
    int p = calcPartial( idx, partial );
    if( calcOpt( idx, p ) > maxTraffic )
        dfs( idx+1, p );
    v[idx] = false;
    p = calcPartial( idx, partial );
    if( calcOpt( idx, p ) > maxTraffic )
        dfs( idx + 1, p );
}

void calcRemain(){
    int cnt,p,q,sum = 0, asum = 0;
    priority_queue< int, vector<int>, greater<int> > Q;
    vector<int> v;
    v.reserve( 200 );
    
    remain[n] = remain[n-1] = 0;
    for( int i=n-2; i>-1; --i ){
        cnt = n - i;
        p = cnt >> 1;
        q = cnt - p;
        cnt = ( (p * (p-1) ) >> 1 ) + ( (q*(q-1)) >> 1 );
        for( int j=i+1; j<n; ++j ){
            Q.push( c[i][j] );
            sum += c[i][j];
        }
        remain[i] = sum;
        while(cnt--){
            v.push_back( Q.top() );
            remain[i] -= Q.top();
            Q.pop();
        }
        while( !v.empty() ){
            Q.push( v.back() );
            v.pop_back();
        }
    }
}

int main(){

    while( ~scanf( "%d", &n ) ){
        for( int i=0; i<n; ++i ){
            for( int j=0; j<n; ++j ){
                scanf( "%d", &c[i][j] );
            }
        }
        num = 0;
        maxTraffic = 0;
        calcRemain();
        v[0] = true;
        dfs( 1, 0 );
        printf( "%d\n", maxTraffic );
    }
    return 0;
}

• Re:想了一个给力的剪枝，附上0MS代码 (10) Smile_7 2013-03-23 21:15:04