记录编号	38334	评测结果	AAAAAATTTAAAAAATA
题目名称	牛棚的灯	最终得分	76
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	5.330 s
提交时间	2012-04-17 16:01:28	内存使用	0.27 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
int n,m,f[40]={0};
bool used[40]={0};
typedef vector<int>vec;
vec a[40];
int w[40],answer=100;
void dfs(int x,int y,int z);
int main()
{
	freopen ("lights.in","r",stdin);
	freopen ("lights.out","w",stdout);
	cin>>n>>m;
	for (int i=0;i<m;i++)
	{
		int b,c;
		cin>>b>>c;
		a[b].push_back(c);
		a[c].push_back(b);
	}
	for (int i=1;i<=n;i++)
	{
		a[i].push_back(i);
		f[i]=i;
	}
	for (int i=1;i<n;i++)
	{
		for (int j=i+1;j<=n;j++)
		{
			if (a[i].size()<a[j].size())
			{
				int tmp;
				tmp=f[j];
				f[j]=f[i];
				f[i]=tmp;
			}
		}
	}
	dfs(0,0,0);
	cout<<answer;
	return 0;
}
 
void dfs(int x,int y,int z)
{
	if (y==n&&x==n)
	{
		if (z<answer)
			answer=z;
		return;
	}
	if (x==n)
		return;
	if (z>answer)
		return;
	int yy;
	bool use[40]={0};
	yy=y;
	for (int i=1;i<=n;i++)
		use[i]=used[i];
	for (int i=0;i<2;i++)
	{
		if (i==1)
		{
			x++;
			for (int j=0;j<a[f[x]].size();j++)
			{
				if (used[a[f[x]][j]])
				{
					used[a[f[x]][j]]=0;
					y--;
				}
				else 
				{
					if(!used[a[f[x]][j]])
					{
						used[a[f[x]][j]]=1;
						y++;
					}
				}
			}
			dfs(x,y,z+1);
			x--;
			y=yy;
			for (int i=1;i<=n;i++)
				used[i]=use[i];
		}
		if (i==0)
		{
			dfs(x+1,y,z);
		}
		y=yy;
		for (int i=1;i<=n;i++)
			used[i]=use[i];
	}
}