Description
A university network is composed of N computers. System administrators gathered information on the traffic between nodes, and carefully divided the network into two subnetworks in order to minimize traffic between parts.
A disgruntled computer science student Vasya, after being expelled from the university, decided to have his revenge. He hacked into the university network and decided to reassign computers to maximize the traffic between two subnetworks.
Unfortunately, he found that calculating such worst subdivision is one of those problems he, being a student, failed to solve. So he asks you, a more successful CS student, to help him.
The traffic data are given in the form of matrix C, where Cij is the amount of data sent between ith and jth nodes (Cij = Cji, Cii = 0). The goal is to divide the network nodes into the two disjointed subsets A and B so as to maximize the sum ∑Cij (i∈A,j∈B).
A disgruntled computer science student Vasya, after being expelled from the university, decided to have his revenge. He hacked into the university network and decided to reassign computers to maximize the traffic between two subnetworks.
Unfortunately, he found that calculating such worst subdivision is one of those problems he, being a student, failed to solve. So he asks you, a more successful CS student, to help him.
The traffic data are given in the form of matrix C, where Cij is the amount of data sent between ith and jth nodes (Cij = Cji, Cii = 0). The goal is to divide the network nodes into the two disjointed subsets A and B so as to maximize the sum ∑Cij (i∈A,j∈B).
Input
The first line of input contains a number of nodes N (2 <= N <= 20). The following N lines, containing N space-separated integers each, represent the traffic matrix C (0 <= Cij <= 10000).
Output file must contain a single integer -- the maximum traffic between the subnetworks.
Output file must contain a single integer -- the maximum traffic between the subnetworks.
Output
Output must contain a single integer -- the maximum traffic between the subnetworks.
Sample Input
3 0 50 30 50 0 40 30 40 0
Sample Output
90
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 int map[21][21]; 6 int flag[21]; 7 int N; 8 int maxS; 9 void dfs(int step) 10 { 11 if(step==N) 12 { 13 int sum=0; 14 int i,j; 15 for(i=0;i<N;i++) 16 { 17 for(j=0;j<N;j++) 18 { 19 if(flag[i] && !flag[j]) 20 { 21 sum+=map[i][j]; 22 } 23 } 24 } 25 if(sum>maxS) 26 { 27 maxS=sum; 28 } 29 return; 30 } 31 flag[step]=false; 32 dfs(step+1); 33 flag[step]=true; 34 dfs(step+1); 35 } 36 int main() 37 { 38 while(~scanf("%d",&N)) 39 { 40 int i,j; 41 for(i=0;i<N;i++) 42 { 43 for(j=0;j<N;j++) 44 { 45 scanf("%d",&map[i][j]); 46 } 47 } 48 memset(flag,false,sizeof(flag)); 49 maxS=0; 50 flag[0]=false; 51 dfs(1); 52 printf("%d\n",maxS); 53 } 54 return 0; 55 }
这个题目主要是理解题目意思。
题目意思是说：有一个集合（1,2,3），把这个集合分成两个子集合，然后求这两个子集合之间的值得和。
举例说明一下：
测试数据有3台电脑，即（1,2,3），
我们可以分成（1,2）和（3），或者（1，3）和（2），或者（2,3）和（1），然后求每一种可能的值，去最大的那个的值。
如何求值呢？
第一种可能：1和3之间的值为30,2和3之间的值为40，所以和是70；
第二种可能：1和2之间的值为50,3和2之间的值为40，所以和是90；
第三种可能：2和1之间的值为50,3和1之间的值为30，所以和是80；
即90最大，所以输出90；
理解意思了就直接dfs，因为数据范围不是很大，可以不需要剪枝就能AC。