\(\color{#0066ff}{题目描述}\)

贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿，突然，牛棚的电源跳闸了，所有的灯都被关闭了。贝希是一个很胆小的女生，在伸手不见拇指的无尽的黑暗中，她感到惊恐，痛苦与绝望。她希望您能够帮帮她，把所有的灯都给重新开起来！她才能继续快乐地跟她的闺密们继续玩游戏！ 牛棚中一共有N（1 <= N <= 35）盏灯，编号为1到N。这些灯被置于一个非常複杂的网络之中。有M（1 <= M <= 595）条很神奇的无向边，每条边连接两盏灯。 每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候，这盏灯本身，还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是：当一盏灯是开著的时候，这盏灯被关掉；当一盏灯是关著的时候，这盏灯被打开。 问最少要按下多少个开关，才能把所有的灯都给重新打开。 数据保证至少有一种按开关的方案，使得所有的灯都被重新打开。

\(\color{#0066ff}{输入格式}\)

• Line 1: Two space-separated integers: N and M.

• Lines 2..M+1: Each line contains two space-separated integers representing two lights that are connected. No pair will be repeated.

\(\color{#0066ff}{输出格式}\)

• Line 1: A single integer representing the minimum number of switches that need to be flipped in order to turn on all the lights.

\(\color{#0066ff}{输入样例}\)

5 6

1 2

1 3

4 2

3 4

2 5

5 3

\(\color{#0066ff}{输出样例}\)

3

\(\color{#0066ff}{题解}\)

看n的范围，显然可以对抗搜索

用\(O(2^n)\)枚举出前半部分的点选或不选，并记录到达状态的最小步数（用map）

再搜后半部分点选或不选，只要能跟刚刚的拼上，就更新答案

#include<cstdio>

#include<queue>

#include<vector>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<map>

#define _ 0

#define LL long long

#define Space putchar(' ')

#define Enter putchar('\n')

#define fuu(x,y,z) for(int x=(y),x##end=z;x<=x##end;x++)

#define fu(x,y,z)  for(int x=(y),x##end=z;x<x##end;x++)

#define fdd(x,y,z) for(int x=(y),x##end=z;x>=x##end;x--)

#define fd(x,y,z)  for(int x=(y),x##end=z;x>x##end;x--)

#define mem(x,y)   memset(x,y,sizeof(x))

#ifndef olinr

inline char getc()

{

    static char buf[100001],*p1=buf,*p2=buf;

    return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100001,stdin),p1==p2)? EOF:*p1++;

}

#else

#define getc() getchar()

#endif

template<typename T>inline void in(T &x)

{

    int f=1; char ch; x=0;

    while(!isdigit(ch=getc()))(ch=='-')&&(f=-f);

    while(isdigit(ch)) x=x*10+(ch^48),ch=getc();

    x*=f;

}

int n,m;

std::map<LL,int> mp;

LL zt[55];

int mid;

int ans=0x7fffffff;

inline void dfs1(int now,LL z,int step)

{

	if(now==mid+1)

	{

		if(!mp.count(z)) mp[z]=step;

		else mp[z]=std::min(mp[z],step);

		return;

	}

	dfs1(now+1,z^zt[now],step+1);

	dfs1(now+1,z,step);

}

inline void dfs2(int now,LL z,int step)

{

	if(now==n+1)

	{

		if(mp.count(z)) ans=std::min(ans,step+mp[z]);

		return;

	}

	dfs2(now+1,z^zt[now],step+1);

	dfs2(now+1,z,step);

}

int main()

{

    in(n),in(m);

    int x,y;

    fuu(i,1,m) in(x),in(y),zt[x]|=1LL<<(y-1),zt[y]|=1LL<<(x-1);

	fuu(i,1,n) zt[i]|=(1<<(i-1));

    mid=(1+n)>>1;

    dfs1(1,(1LL<<n)-1,0);

    dfs2(mid+1,0LL,0);

    printf("%d",ans);

    return ~~(0^_^0);

}