烟台市做网站找哪家好/企业网站模板图片

http://poj.org/problem?id=2531

题意 ：有N台电脑,每两台电脑之间都有个通信量C[i][j]; 问如何将其分成两个子网，能使得子网之间的通信量最大. 也就是说将所有节点分为两个子集，A,B。求A的各个元素与B的各个元素之间距离的和。

思路：分类在搜索里，一开始也没看懂题，后来连人家的题解都看不懂，这个就像是翻黑白棋问题，一个点要么属于A，要么属于B，只要枚举出所有的状态来就行了

#include <iostream>
#include <string.h>
#include <stdio.h>int dis[31][31] ;
int sum ;
int flag[121] ;
int N ;using namespace std ;void dfs(int num,int sum1)
{if(num == N){if(sum1 > sum)sum = sum1 ;return  ;}flag[num] = 0 ;//这个点不属于Aint sum2 = 0 ;for(int i = 0 ; i < num ; i++){if(flag[i])//i这个点属于A，就要求出num这个点与这些点的距离和sum2 += dis[num][i] ;}dfs(num+1,sum1 + sum2) ;flag[num] = 1 ;//这个点不属于Bsum2 = 0 ;for(int i = 0 ; i < num ; i++){if(!flag[i])sum2 += dis[num][i] ;}dfs(num+1,sum1+sum2) ;}
int main()
{scanf("%d",&N) ;for(int i = 0 ; i < N ; i++)for(int j = 0 ; j < N ; j++)scanf("%d",&dis[i][j]) ;memset(flag,0,sizeof(flag)) ;sum  = -9999999 ;dfs(0,0) ;printf("%d\n",sum) ;return 0 ;
}