题目大意：给定一个n个点的无向图，，要求将点集分成大小相等的两个子集，使两个子集之间的边数最少
n<=26，直接C(26,13)枚举也只有1000W(其实去掉重复的只有500W，我写代码时脑残忘去掉了)
但是常规的枚举方法每次需要O(n)统计答案，显然会T
这里我们考虑搜索
初始令S集为空，T集包含全部的点，然后依次枚举T的某个点加入S集
这个点加入S集时，与S集的连边需要从答案中扣除，与T集的连边需要加入答案
因此我们将一个点连出的所有边用一个二进制数表示 那么取交集就是连边的数量
预处理一下每个数的二进制表示有多少位即可
P.S. 我一开始预处理了[0,2^26)的位数，结果数组太大BZ上T到死，交到Main上直接MLE
因此我们预处理[0,2^13)的位数，然后把那个[0,2^26)之间的数拆成两半即可
时间复杂度O(C(n,n/2))
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 30using namespace std;int n,m,a[M];char digit[1<<13];int ans=0x3f3f3f3f,ans_sta;int Digit(int x){return digit[x&(1<<n/2)-1]+digit[x>>n/2];}void DFS(int now,int pos,int sta,int cnt){if(now==n/2){if(cnt<ans)ans=cnt,ans_sta=sta;return ;}int i;for(i=pos;i<=n-(n/2-now)+1;i++)DFS(now+1,i+1,sta|(1<<i-1),cnt-Digit(sta&a[i])+Digit(~sta&a[i]));}int main(){int i,x,y;cin>>n>>m;for(i=1;i<=m;i++){scanf("%d%d",&x,&y);a[x]|=(1<<y-1);a[y]|=(1<<x-1);}for(i=1;i<1<<(n>>1);i++)digit[i]=digit[i>>1]+(i&1);DFS(0,1,0,0);for(i=1;i<=n;i++)if(ans_sta&(1<<i-1))printf("%d ",i);return 0;}
最大的成功在于最大的付出。
