POJ 2531 Network Saboteur

浏览数：18 / 时间：2015年06月09日

【题意简述】：现在已知，你可以从键盘输入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,古老的榕树,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

POJ 2531 Network Saboteur