POJ 2531 Network Saboteur （枚举+剪枝）

#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=21;
int n;
int w[maxn][maxn];
//int vis[maxn];
int visit[550000*2];
int ans=0;
int set1[maxn];
int set2[maxn];
int idx1,idx2;
int main()
{
    int l;
    //cout<<(1<<20)<<endl;
    cin>>n;

    memset(w,0,sizeof(w));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            scanf("%d",&l);
        for(int j=i+1;j<=n;j++){
            scanf("%d",&l);
            w[i][j]=w[j][i]=l;
        }
    }
    memset(vis,0,sizeof(vis));
    memset(visit,0,sizeof(visit));
    int all=1<<n-1;
    ans=0;
    //用状态压缩来枚举两组的情况
    for(int i=1;i<(1<<n)-1;i++){
        //对称的就不需要再考虑了，如101和010，只要考虑其中一个就可以了，用异或即可求出对称的状态。
        if(!visit[all^i]){
            visit[i]=1;
            idx1=idx2=0;
            //将编号存入两个数组中去，而不是用vis标记，从原本的1000+ms减少到297ms
            for(int j=0;j<n;j++){
                if(i&(1<<j))
                    set1[idx1++]=j+1;
                else
                    set2[idx2++]=j+1;
            }
            int tot=0;
            for(int k=0;k<idx1;k++){
                for(int t=0;t<idx2;t++){
                    tot+=w[set1[k]][set2[t]];
                }
            }
            if(tot>ans)
                ans=tot;
        }
    }
    printf("%d\n",ans);
    return 0;
}

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
/*
AC
dfs暴力枚举 547ms
*/
using namespace std;
const int maxn=21;
int n;
int w[maxn][maxn];
int vis[maxn];
int set1[maxn];
int set2[maxn];
int idx1,idx2;
int ans=0;
void dfs(int u){
    if(u==n+1){
        int tot=0;
        idx1=idx2=0;
        for(int i=1;i<=n;i++){
            if(vis[i])
                set1[idx1++]=i;
            else
                set2[idx2++]=i;
        }
        for(int k=0;k<idx1;k++){
            for(int t=0;t<idx2;t++){
                tot+=w[set1[k]][set2[t]];
            }
        }
        if(tot>ans)
            ans=tot;
        return ;
    }
    vis[u]=0;
    /*
    之前还用for循环，额，脑残了。。。
    for(int i=u+1;i<=n+1;i++){
        dfs(i);
    }
    */
    dfs(u+1);
    vis[u]=1;
    dfs(u+1);

}
int main()
{
    int l;
    cin>>n;
    //cout<<(1<<19)<<endl;
    memset(w,0,sizeof(w));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            scanf("%d",&l);
        for(int j=i+1;j<=n;j++){
            scanf("%d",&l);
            w[i][j]=w[j][i]=l;
        }
    }
    memset(vis,0,sizeof(vis));
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

#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=21;
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+1){
        ans=Sum;
    }
    else{
        int sum=0;
        for(int i=0;i<idx1;i++){
            sum+=w[set1[i]][k];
        }
        set1[idx1]=k;  //若k属于第一个集合
        dfs(Sum+sum,idx1+1,idx2,k+1);

        sum=0;
        for(int i=0;i<idx2;i++){
            sum+=w[set2[i]][k];
        }
        set2[idx2]=k; //若k属于第二个集合
        dfs(Sum+sum,idx1,idx2+1,k+1);
    }
}
int main()
{
    int l;
    cin>>n;
    memset(w,0,sizeof(w));
    tot=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            scanf("%d",&l);
        for(int j=i+1;j<=n;j++){
            scanf("%d",&l);
            w[i][j]=w[j][i]=l;
            tot+=l;
        }
    }
    tot1=0;
    for(int i=1;i<n/2;i++){
        for(int j=i+1;j<n/2;j++)
            tot1+=w[i][j];
    }
    tot2=0;
    for(int i=n/2;i<=n;i++){
        for(int j=i+1;j<=n;j++)
            tot2+=w[i][j];
    }
    ans=tot1+tot2;
    idx1=idx2=0;
    set1[0]=1; //先把1固定为第一个集合
    dfs(0,1,0,2);
    printf("%d\n",tot-ans);
    return 0;
}