个人心得：对于深搜的使用还是不到位，对于递归的含义还是不太清楚！本来想着用深搜构成一个排列，然后从一到n分割成俩个数组，然后后面发现根本实现不了，思路太混乱。后来借鉴了网上的思想，发现用数组来标志，当值等于一时就属于A数组，等于0时属于B数组，这样就可以构成递归，即下一个数只有在A数组和不在A数组，发现这个思想真的挺好的。
DFS心得：若从第二步开始，动作变得程序化，像地图，只有上下左右，这个是只有为0不为0是就可以用深搜递归思想解决。
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
解题思路：题目大意：给定一个邻接矩阵，要求将顶点分为A,B两个集合，使得A集合中的所有顶点到B集合所有顶点的距离之和为最大。
首先两个集合的表示用一个一维数组A[]，其中A[i]=1，表示节点i在集合A中，为0则在集合B中。
二位数组C[][]存储邻接矩阵,
由于每一个数字有两种选择0和1，结构适用深度优先：从第一个数开始A[0]=1（假设0号顶点一定在集合A中），
对0来说第2个顶点有两种情况，依次类推，结构就出来了。递归出口就是到达第n-1号顶点。
求和用两个for循环加上对存在集合的判定，记录最大值，每次求和结果与最大值比较，如果更大则修改最大值。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 using namespace std; 6 int n; 7 int sum; 8 int a[21][21]; 9 int A[21]; 10 void dfs(int step) 11 { 12 if(step>n) 13 { 14 int t=0; 15 for(int i=1;i<=n;i++) 16 { 17 if(A[i]==1) 18 for(int j=1;j<=n;j++) 19 { 20 if(A[j]==0) 21 t+=a[i][j]; 22 23 } 24 } 25 if(sum==0) sum=t; 26 if(sum<t) sum=t; 27 return ; 28 } 29 A[step]=1; 30 dfs(step+1); 31 A[step]=0; 32 dfs(step+1); 33 return ; 34 } 35 int main() 36 { 37 cin>>n; 38 sum=0; 39 memset(A,0,21); 40 for(int i=1;i<=n;i++) 41 for(int j=1;j<=n;j++) 42 cin>>a[i][j]; 43 dfs(1); 44 cout<<sum<<endl; 45 return 0; 46 47 48 49 50 51 52 }