记录编号	58719	评测结果	AAAAAAAAAAAAAAAAA
题目名称	牛棚的灯	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2013-04-25 10:24:07	内存使用	3.16 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int N,M;
int map[50][50];
int L[50];
int minn;
void init(){
	freopen("lights.in","r",stdin);
	freopen("lights.out","w",stdout);
	scanf("%d%d",&N,&M);
	memset(map,0,sizeof(map));
	int x,y;
	for (int i=1;i<=M;i++){
		scanf("%d%d",&x,&y);
		map[x][y]=1;
		map[y][x]=1;
	}
	for (int i=1;i<=N;i++){
		map[i][N+1]=1;
		map[i][i]=1;
	}
}
void swap(int x,int y){
	int tmp;
	for (int i=1;i<=N+1;i++){
		tmp=map[x][i];
		map[x][i]=map[y][i];
		map[y][i]=tmp;
	}
}
void prin(){
	for (int i=1;i<=N;i++){
		for (int j=1;j<=N+1;j++)
			printf("%d ",map[i][j]);
		printf("\n");
	}
	printf("\n");
}
void dfs(int k,int now){
	if (now>=minn) return ;
	if (k==0){
		int ans=0;
		for (int i=1;i<=N;i++)
			if (L[i]) ans++;
		if (ans<minn) minn=ans;
	}else{
		int tmp;
		tmp=0;
		if (map[k][k]==1){
			for (int j=k+1;j<=N;j++){
				tmp=tmp^(map[k][j]*L[j]);
			}
			L[k]=tmp^map[k][N+1];
			dfs(k-1,now+L[k]);
		}
		else{
			L[k]=1;
			dfs(k-1,now+1);
			L[k]=0;
			dfs(k-1,now);
		}
	}
}
void work(){
//	prin();
	int p;
	for (int i=1;i<=N;i++){
		p=i-1;
		while (map[++p][i]==0 && p<=N);
		swap(p,i);
		for (int j=i+1;j<=N;j++)
			if (map[j][i])
			for (int k=i;k<=N+1;k++)
				map[j][k]=map[j][k]^map[i][k];
	}
	memset(L,0,sizeof(L));
	
//	prin();
	minn=200000000;
	dfs(N,0);/*
	for (int i=N-2;i>=1;i--){
		
		for (int j=i+1;j<=N;j++){
			tmp=tmp^(map[i][j]*L[j]);
		}
		L[i]=tmp^map[i][N+1];
		if (map[i][i]==0) L[i]=1;
	}
	*/
	printf("%d",minn);
}
int main()
{
	init();
	work();
	return 0;
}