BZOJ1130: [POI2008]POD Subdivision of Kingdom 状压+dfs+恶心题

题解：

这题做的恶心死我了。。。

简直是要多恶心有多恶心。。。

将我为数不多的信心消磨殆尽。。。

完全照着大爷题解，大家去看大爷题解吧。。。

不过有几点补充：

（1）在$O(\binom{n}{m})$时间内找出所有组合：

我们依次确定每个元素选不选，进行dfs，如果当前已经是一个叶子节点直接返回（剩下的全部选择才刚好$m$个），否则就搞两个分支下去。

这样的话是一棵二叉树，且每一个叶子都是一种方案，于是就是线性的咯。

当然我自己就没这样写了。

（2）如果允许重边的话看起来就没这样容易了？

代码：

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 26
int s[N];
int n,m;
int c[1<<13];
int f(int x){
	return c[x&((1<<(n>>1))-1)]+c[x>>(n>>1)];
}
int ans=0x3f3f3f3f,re;
void dfs(int lastnum,int lastpos,int lasts,int lastans){
	if(lastnum==(n>>1)){
		if(ans>lastans){
			ans=lastans;
			re=lasts;
		}
		return;
	}
	for(int i=lastpos+1;i<n;++i)
		dfs(lastnum+1,i,lasts|(1<<i),lastans-f(s[i]&lasts)+f(s[i]&(((1<<n)-1)^lasts)));
}
int main(){
#ifndef ONLINE_JUDGE
	//freopen("tt.in","r",stdin);
#endif
	cin>>n>>m;
	int i,j,a,b;
	while(m--){
		scanf("%d%d",&a,&b);
		--a;
		--b;
		s[a]|=1<<b;
		s[b]|=1<<a;
	}
	for(i=1;i<(1<<(n>>1));++i)
		c[i]=c[i>>1]+(i&1);
	dfs(0,-1,0,0);
	if(~re&1)
		re^=((1<<n)-1);
	for(i=0;i<n;++i)
		if((re>>i)&1)
			printf("%d ",i+1);
	return 0;
}