自己一开始没咋看明白，很多知识点都不知道。
转载两份代码。
第一份：
出处：http://exp-blog.com
大佬思想：
题目大意：
把一个完全图分成两部分，使得连接这两部分边的权和最大。
解题思路：
图论的无向完全图的最大割问题 （做网络最大流的时候同学们应该看过最小割，所以别问我什么是最大割了。。。不懂的百度去。。。）
可以用 随机化算法 Random Algorithm 去做
一开始我没读懂题，以为是求最大权。。。傻呼呼的用最了最小生成树的算法去做= =
一直RERERE。。。还以为是数组开得不够大。。。悲剧啊。。。
虽然是图论，但不懂得为什么人家要把这题归类到 搜索题 去，用搜索我完全没思路去做。。。。 额，不多说，详细思路看我的程序，解释非常详尽
//Memory Time
//188K 375MS #include<iostream>
using namespace std;const int TimeLimit=2000; //本题时间限制为2000msint main(int i,int j)
{int n;while(cin>>n){/*Input*/int w[30][30]={0};for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>w[i][j];w[j][i]=w[i][j]; //双向完全图}/*Random Algorithm*/bool subset[30]={false}; //A集:true B集:falseint time=TimeLimit*100; //使随机次数尽可能大，随机结果尽可能接近最优解long max_w=0; //最大割的权值之和long sum=0; //当前边割集权和while(time--){int x=rand()%n+1; //生成随机数 x，对应于总集合的某个结点x//注意由于使用的结点序号为1~n，对应了数组下标，下标为0的数组元素没有使用//那么这里必须+1，因为若rand()=n，那么再对n取模结果就为0//这时就会导致使用了不存在的 [0]结点，本应使用的 [n]结点就被丢弃了subset[x]=!subset[x]; //改变x所在的集合位置for(int i=1;i<=n;i++) //由于是完全图，所以每个顶点i都与x相关联，因此要全部枚举{if(subset[i]!=subset[x]) //结点i 和 x分别在两个集合内sum+=w[i][x]; //就是说因为x所在集合的改变，使得割边的个数增加//割集的原权值 要加上 当前新加入的割边(i,x)的权值if(i!=x && subset[i]==subset[x]) //结点i 和 x分别在相同的集合内，但他们不是同一元素sum-=w[i][x]; //就是说因为x所在集合的改变，使得割边的个数减少//割集的原权值 要减去 当前失去的割边(i,x)的权值}if(max_w < sum)max_w = sum;}cout<<max_w<<endl;}return 0;
}
第二份：
出处：https://blog.csdn.net/martin31hao/article/details/8098302?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160213246719724848314395%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=160213246719724848314395&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduend~default-3-8098302.pc_first_rank_v2_rank_v28_p&utm_term=POJ+2531&spm=1018.2118.3001.4187
在8月份做过两遍这道题，做第一次的时候觉得这道题DFS的想法还挺新颖的。做第二次的时候，貌似就已经忘了思路了，这次在CAI的解题表格里又看到了这道题，出于练手的想法，就又做了一遍。
题目大意：有n个点，把这些点分别放到两个集合里，在两个集合的每个点之间都会有权值，求可能形成的最大权值。
思路：1、把这两个集合标记为0和1，先默认所有点都在集合0里。
2、依次枚举每个点id，把每个点都放到集合1里去，这个时候就要调整集合的权值了，原来和id都在集合0里的点，要把权值加上；而在集合1里的点，要把权值减去。3、权值调整完毕后，和ans比较，如果比ans要大， 调整ans。4、如果放到集合1中，调整节点后的权值比放在集合0中要大，那么就默认这个点在集合1中，继续枚举下面的点进行DFS。最终是可以把最有状态都枚举出来的。
#include<cstdio>
#include<cstring>
using namespace std;const int maxn = 30;
int n, ans;
int a[maxn][maxn];
int dep[maxn];void dfs(int id, int data)
{dep[id] = 1;int tmp = data;for(int i = 1; i <= n; i ++){if(dep[i] == 0)tmp += a[i][id];elsetmp -= a[i][id];}if(ans < tmp)ans = tmp;for(int i = id + 1; i <= n; i ++){if(tmp > data){dfs(i, tmp);dep[i] = 0;}}
}int main()
{while(~scanf("%d", &n)){for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++)scanf("%d", &a[i][j]);memset(dep, 0, sizeof(dep));ans = 0;dfs(1, 0);printf("%d\n", ans);}
}
