POJ 2531 Network Saboteur

【题意简述】：现在已知，你可以从键盘输入n，它代表着n个点，然后输入n个点之间的关系！就是那个邻接矩阵。邻接矩阵的每个值代表其点与点之间的权值！现在让我们把这些点分成两部分，使得这两部分的权值之和最大！每个部分之内的点与点之间权值算作0！

【思路】：我们可以试着先将这些点都放在一个部分里，然后再依次拿出这些点，放到另一个集合里，计算此时的权值之和！和之前计算的权值作比较，如果比之前大，就更新这个值！

详见代码：（code from：http://blog.csdn.net/martin31hao/article/details/8098302）

#include<iostream>
using namespace std;
const int Max = 21;
const bool A = true;
const bool B = false;
 
int n, map[Max][Max], ans = 0;
bool set[Max];
 
void dfs(int dep, int sum){
    if(dep > n){
        if(sum > ans)
            ans = sum;
        return;
    }
 
    int i, m;
    m = 0;
    set[dep] = A;
    for(i = 1; i <= dep; i ++)
        if(set[i] == B)
            m += map[i][dep];
    dfs(dep + 1, sum + m);
 
    m = 0;
    set[dep] = B;
    for(i = 1; i <= dep; i ++)
        if(set[i] == A)
            m += map[i][dep];
    dfs(dep + 1, sum + m);
}
 
int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin >> map[i][j];
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

POJ 2531 Network Saboteur,布布扣,bubuko.com

POJ 2531 Network Saboteur

原文：http://blog.csdn.net/u013749862/article/details/23023425