题意：给你一个图，图中点之间会有边权，现在问题是把图分成两部分，使得两部分之间边权之和最大。
目前我所知道的有四种做法：
方法一：状态压缩
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
/*
用状态压缩枚举，297ms。 题意：给你一个图，图中点之间会有边权，现在问题是把图分成两部分，使得两部分之间边权之和最大。 情况是对称的，也就是说枚举所有的分类情况中，有一半是冗余的。
举个例子来说，有5个节点，1、2、3分配为A组，4、5分配给B组，
这个分类的策略所计算的结果和1、2、3分配为B组，4、5分配给A组是一样的。
因此对称的就不需要再考虑了，如状态压缩时101和010，只要考虑其中一个就可以了。
至于当枚举到一个状态时，怎么判断它的对称状态已经枚举过了，采用异或就可以了。 */
using namespace std;
const int maxn=;
int n;
int w[maxn][maxn];
//int vis[maxn];
int visit[*];
int ans=;
int set1[maxn];
int set2[maxn];
int idx1,idx2;
int main()
{
int l;
//cout<<(1<<20)<<endl;
cin>>n; memset(w,,sizeof(w));
for(int i=;i<=n;i++){
for(int j=;j<=i;j++)
scanf("%d",&l);
for(int j=i+;j<=n;j++){
scanf("%d",&l);
w[i][j]=w[j][i]=l;
}
}
memset(vis,,sizeof(vis));
memset(visit,,sizeof(visit));
int all=<<n-;
ans=;
//用状态压缩来枚举两组的情况
for(int i=;i<(<<n)-;i++){
//对称的就不需要再考虑了，如101和010，只要考虑其中一个就可以了，用异或即可求出对称的状态。
if(!visit[all^i]){
visit[i]=;
idx1=idx2=;
//将编号存入两个数组中去，而不是用vis标记，从原本的1000+ms减少到297ms
for(int j=;j<n;j++){
if(i&(<<j))
set1[idx1++]=j+;
else
set2[idx2++]=j+;
}
int tot=;
for(int k=;k<idx1;k++){
for(int t=;t<idx2;t++){
tot+=w[set1[k]][set2[t]];
}
}
if(tot>ans)
ans=tot;
}
}
printf("%d\n",ans);
return ;
}
方法二：dfs枚举
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
/*
AC
dfs暴力枚举 547ms
*/
using namespace std;
const int maxn=;
int n;
int w[maxn][maxn];
int vis[maxn];
int set1[maxn];
int set2[maxn];
int idx1,idx2;
int ans=;
void dfs(int u){
if(u==n+){
int tot=;
idx1=idx2=;
for(int i=;i<=n;i++){
if(vis[i])
set1[idx1++]=i;
else
set2[idx2++]=i;
}
for(int k=;k<idx1;k++){
for(int t=;t<idx2;t++){
tot+=w[set1[k]][set2[t]];
}
}
if(tot>ans)
ans=tot;
return ;
}
vis[u]=;
/*
之前还用for循环，额，脑残了。。。
for(int i=u+1;i<=n+1;i++){
dfs(i);
}
*/
dfs(u+);
vis[u]=;
dfs(u+); }
int main()
{
int l;
cin>>n;
//cout<<(1<<19)<<endl;
memset(w,,sizeof(w));
for(int i=;i<=n;i++){
for(int j=;j<=i;j++)
scanf("%d",&l);
for(int j=i+;j<=n;j++){
scanf("%d",&l);
w[i][j]=w[j][i]=l;
}
}
memset(vis,,sizeof(vis));
dfs();
printf("%d\n",ans);
return ;
}
方法三：大牛的解法
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
/*
看了discuss里大牛的做法，然后自己打了一遍，16ms
以下来自discuss里的： 1.等价剪枝：根据对称性剪枝
举个例子来说，有5个节点，1、2、3分配为A组，4、5分配给B组，
这个分类的策略所计算的结果和1、2、3分配为B组，4、5分配给A组是一样的。
那么怎么去除这一半的冗余呢，其实很简单，我们强制第1个节点分配给A组，
那么后面不管怎么分，全体情况都不会有重复的了。 2.换个角度，更高效搜索算法 ：如本题逆向思维求最小内部代价
本题要求两个集合之间的边权和最大。反过来，相当于两个集合内部点之间的边权和最小，
令该和为ans。那么我们dfs的目的就是使得ans的值最小。 3.无法达最优：提前剪枝，也就是如果当前的Sum>=ans，就不必继续下去了
*/
using namespace std;
const int maxn=;
int n;
int w[maxn][maxn];
int set1[maxn];
int set2[maxn];
int idx1,idx2;
int tot1,tot2,tot;
int ans; void dfs(int Sum,int idx1,int idx2,int k){
if(Sum>=ans)
return;
else if(k==n+){
ans=Sum;
}
else{
int sum=;
for(int i=;i<idx1;i++){
sum+=w[set1[i]][k];
}
set1[idx1]=k; //若k属于第一个集合
dfs(Sum+sum,idx1+,idx2,k+); sum=;
for(int i=;i<idx2;i++){
sum+=w[set2[i]][k];
}
set2[idx2]=k; //若k属于第二个集合
dfs(Sum+sum,idx1,idx2+,k+);
}
}
int main()
{
int l;
cin>>n;
memset(w,,sizeof(w));
tot=;
for(int i=;i<=n;i++){
for(int j=;j<=i;j++)
scanf("%d",&l);
for(int j=i+;j<=n;j++){
scanf("%d",&l);
w[i][j]=w[j][i]=l;
tot+=l;
}
}
tot1=;
for(int i=;i<n/;i++){
for(int j=i+;j<n/;j++)
tot1+=w[i][j];
}
tot2=;
for(int i=n/;i<=n;i++){
for(int j=i+;j<=n;j++)
tot2+=w[i][j];
}
ans=tot1+tot2;
idx1=idx2=;
set1[]=; //先把1固定为第一个集合
dfs(,,,);
printf("%d\n",tot-ans);
return ;
}
方法四：随机算法