poj2531(深搜剪枝)

题意就是把节点分成A、B两组，节点间距C给了，要求解分组的方法，使得∑Cij (i∈A,j∈B)最大。

首先把所有节点都放在一组，然后采用深度优先搜索的方法，对每一个节点都做判断是否应该移到另一组去，判断的依据是移过去和不移过去哪个得到的和值比较大（这里移去B组后的计算方法就是加上该点和在A组中的所有点的间距，和减去原本就在B组中的所有点的间距），如果移过去变小了，那么则不移过去，并剪掉该条支路。

DFS的本质就是枚举，一种递归的枚举。比如如果这个程序里面不剪枝的话就可以枚举到所有的分组情况。剪枝是优化的方法，对满足一定条件的做出判断，认为枚举下去已经没有意义，所以剪掉其分支。

#include <iostream>

using namespace std;

const int MAX_N = ;

int n;

int map[MAX_N + ][MAX_N + ];

bool in_group[MAX_N + ];

int ans;

void dfs(int id, int cur_sum)

{

    in_group[id] = true;

    int tmp_sum = cur_sum;

    for (int i = ; i <= n; i++){

        if (in_group[i]){

            tmp_sum -= map[id][i];

        }

        else{

            tmp_sum += map[id][i];

        }

    }

    if (tmp_sum > ans){

        ans = tmp_sum;

    }

    if (tmp_sum > cur_sum){

        for (int i = id + ; i <= n; i++){

            dfs(i, tmp_sum);

        }

    }

    in_group[id] = false;

}

int main()

{

    cin >> n;

    memset(in_group, , sizeof(in_group));

    ans = ;

    for (int i = ; i <= n; i++){

        for (int j = ; j <= n; j++){

            cin >> map[i][j];

        }

    }

    dfs(, );

    cout << ans << endl;

    return ;

}

巴特西

poj2531(深搜剪枝)

最新文章

热门文章