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;
}