POJ 2531(DFS)
POJ 2531
题目大意，一共N个网络节点，每个节点与其他节点通信需要消耗流量，把这n个节点分为AB两个集合，使得A集合与B集合之间的通讯流量的总和最大。
输入，N + N行N个的数据，输出最大的流量 (N <= 20)
3
0 50 30
50 0 40
30 40 0
思路： 假设最开始所有的都在B集合，通过dfs搜索，将数量从1 - 2 / N 的组合放在A集合，剪枝已经搜索过的组合，搜索一层更新一次流量。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int N, ans = 0, sum = 0;
int mes[30][30];
bool room[30] = { false };
void dfs(int deep,int old){
if(deep == N / 2) return;
for(int i = old + 1;i < N;i++){
int temp = sum;
if(!room[i]) {
room[i] = true;
for(int j = 0;j < N;j++){
if(!room[j]) sum += mes[i][j];
else sum -= mes[i][j];
}
if(sum > ans) ans = sum;
dfs(deep + 1, i);
room[i] = false;
}
sum = temp;
}
}
int main() {
cin >> N;
for(int i = 0;i < N;i++){
for(int j = 0; j < N; j++)
cin >> mes[i][j];
}
memset(room,false,sizeof(room));
dfs(0,-1);
printf("%d\n", ans);
return 0;
}