// poj 2531 Network Saboteur
/*
  求最大,逆向思维，从最小的求。
  思考：对于花费最大的集合A和B，在A和B各自内部的花费和必然最小，如果不是最小，外部最大花费还可以据需增加的。
  所以可以求出集合最小内部花费，然后以总花费减去最小花费即可。
我是参考这个写出来的，但是不知道为什么我的程序跑了47ms
*/
#include <stdio.h>
#include <string.h>

const bool A = true;
const bool B = false;

int c[32][32];
int in[32], out[32];
int n, ans, sum, p;
bool set[32];

void dfs(int k, int s, int ni, int no) // A B 集合内部最小花费
{
    if (s > ans)
        return;
    
    if (k >= n){
        if (s < ans)
            ans = s;
        return;
    }
    
    int t = 0;
    in[ni] = k;
    for (int i = 0; i < ni; i++){
        t += c[in[i]][k];
    }
    dfs(k+1, s+t, ni+1, no);

    t = 0;
    out[no] = k;
    for (int i = 0; i < no; i++){
        t += c[out[i]][k];
    }
    dfs(k+1, s+t, ni, no+1);

}

int main()
{
    scanf("%d", &n);
    sum = 0;
    for (int i = 0; i < n ; i++)
        for (int j = 0; j < n; j++){
            scanf("%d", &c[i][j]);
            sum += c[i][j];
        }
    sum /= 2;
    // 取1..n/2 和 1+n/2..n作为一个最小内部花费界限范围
    p = 0;
    for (int i = 0; i < n/2; i++){
        for (int j = 0; j < n/2; j++)
            p += c[i][j];
    }
    for (int i = n/2; i < n; i++){
        for (int j = n/2; j < n; j++)
            p += c[i][j];
    }
    p /= 2;
    
    ans = p;
    in[0] = 0;
    dfs(1, 0, 1, 0);
    
    printf("%d\n", sum - ans);
    return 0;
}

• Re: 求最大,逆向思维，从最小的求。 (1570) lvzhipu 2012-04-02 00:28:35
• Re: 求最大,逆向思维，从最小的求。 (1570) yaoqijun 2012-10-16 20:27:06