当前位置:首页 » 其他

bzoj-1130 POD

2015-09-15 16:47 本站整理 浏览(78)

题意:给出一个n个结点点的无向图;

选出一个n/2大小的集合,使集合中的元素与非集合中的元素之间的边最少;

n<=26且n为偶数;

输出任意一个集合;

题解:范围26就显然暴搜吧。。

根据calc定理,我们无法在搜索之后O(n)check来过掉这题;

这个复杂度只允许一个搜索;

于是就有了这么一个思路:在搜索的过程中维护答案!

每次选中一个点就相当于是将其从不选集合放到选中集合;

而对于答案的影响是减去它与选中集合的边数,加上它与不选集合的边数;

这个做到O(1),那么这么顺便做答案的复杂度就是可以接受的了;

我们将边表示成邻接矩阵,然后用int状压表示;

如果一个集合也用同样的方法表示,那么与那个点边集做and(&)就是连边的集合了;

统计一个数中1的个数则是预处理一个数组,直接到数组中查;

虽说开不下,但是把数分成两半再查就好了;

代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 27
using namespace std;
int n,ans,cnt=0x3f3f3f3f,cut=(1<<13)-1;
int e
,dig[1<<14];
void init()
{
	for(int i=0;i<1<<14;i++)
		dig[i]=dig[i>>1]+(i&1);
}
int count(int x)
{
	return dig[x>>13]+dig[x&cut];
}
void dfs(int S,int now,int last,int deep)
{
	if(deep==n/2)
	{
		if(cnt>now)
		{
			cnt=now;
			ans=S;
		}
		return ;
	}
	for(int i=last+1;i<=n;i++)
	{
		if(!(S&(1<<i-1)))
		{
			dfs(S|1<<i-1,now-count(S&e[i])+count(~S&e[i]),i,deep+1);
		}
	}
}
void print(int x)
{
	int ret=0,T=~x;
	for(int i=1;x;i++,x>>=1)
	{
		if(x&1)
		{
			ret+=count(e[i]&T);
		}
	}
	printf("%d\n",ret);
}
int main()
{
	int m,i,j,k,x,y;
	scanf("%d%d",&n,&m);
	init();
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		e[x]|=1<<y-1;
		e[y]|=1<<x-1;
	}
	dfs(0,0,0,0);
	for(i=1;ans;i++,ans>>=1)
	{
		if(ans&1)
			printf("%d ",i);
	}
	puts("");
	return 0;
}