BZOJ 1130 POI2008 POD Subdivision of Kingdom DFS

题目大意：给定一个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 30
using 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;
}

BZOJ 1130 POI2008 POD Subdivision of Kingdom DFS

原文：http://blog.csdn.net/popoqqq/article/details/44617891