# 洛谷 P2962 [USACO09NOV]灯Lights

2021年09月15日 阅读数：6

## 题目描述

Bessie and the cows were playing games in the barn, but the power was reset and the lights were all turned off. Help the cows get all the lights back on so they can resume their games.ios

The N (1 <= N <= 35) lights conveniently numbered 1..N and their switches are arranged in a complex network with M (1 <= M <= 595) clever connection between pairs of lights (see below).数组

Each light has a switch that, when toggled, causes that light -- and all of the lights that are connected to it -- to change their states (from on to off, or off to on).网络

Find the minimum number of switches that need to be toggled in order to turn all the lights back on.ide

It's guaranteed that there is at least one way to toggle the switches so all lights are back on.spa

## 输入输出格式

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

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

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

```5 6
1 2
1 3
4 2
3 4
2 5
5 3
```

```3
```

## 说明

There are 5 lights. Lights 1, 4, and 5 are each connected to both lights 2 and 3.it

Toggle the switches on lights 1, 4, and 5.

40分dfs 每盏灯的状态是按仍是不按开关

```#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,m,sumedge,ans,js;

struct Edge{
int x,y,nxt;
Edge(int x=0,int y=0,int nxt=0):
x(x),y(y),nxt(nxt){}
}edge[1300];

}

void dfs(int x,int ste){
bool can=true;
for(int i=1;i<=n;i++)
if(!d[i]){
can=false;
break;
}
if(can){
ans=min(ans,ste);return;
}
if(x==n+1)return;
d[x]=1^d[x];
int v=edge[i].y;
d[v]=1^d[v];
}
dfs(x+1,ste+1);
d[x]=1^d[x];
int v=edge[i].y;
d[v]=1^d[v];
}
dfs(x+1,ste);
}

int main(){
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
}
ans=0x7fffffff;
dfs(1,0);
cout<<ans<<endl;
return 0;
}```

昨天听老徐讲的折半搜索..将hzwer的代码注释了一下....

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define inf 1000000000
#define ll long long
using namespace std;

{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}

bool flag;
int n,m,cnt,mn=inf;
int a[40];
ll ed,p[40],bin[40];
map<ll,int> b;

void dfs(int x,ll now,int used)//x表示搜的第几盏灯，now表示当前的状态，used表示按了几回开关。
{                            //假如now 的二进制表示为 1 1 0 0 1，这里的1表示这盏灯开着。
//而以前的p数组的二进制串的1表示这盏灯的状态改变，哪些灯受影响。
if(x==cnt+1)
{
if(now==ed)mn=min(used,mn);//若是当前状态灯都开着，取最小的步数。
if(!flag)//flag表示第几回搜索，这里是一第一次。
{
int t=b[now];//用stl里的map，来表示以前是否到达过now状态，并记录步数
if(!t||t>used)b[now]=used;//若是以前没有出现过now状态，或者以前出现过，可是以前达到now状
//态的步数比当前的步数大，更新。
}
else                //第二次搜索
{
int t=b[ed-now];//与第一次搜索的状态进行合并。
if(!t)return;//若是在第一次中找不到能和该状态合并的状态，就返回。
mn=min(t+used,mn);//能找到，用第一次搜索的步数和第二次搜索的步数的和更新答案。
}
return;
}
dfs(x+1,now,used);  //不改变当前灯的状态。
dfs(x+1,now^p[x],used+1);//改变当前灯的状态。
}

int main()
{
bin[1]=1;for(int i=2;i<40;i++)bin[i]=bin[i-1]<<1;//bin[i]为2的i-1次方
ed=bin[n+1]-1;//这个ed的做用为判断状态，这个ed的二进制为1 1 1 1 ，表示灯都开着
//当有三盏灯时 ———，当为1 1 1 时用二进制表示是7，
//当有两盏灯时，——，当为1 1 ，用二进制表示是3，就是2^（灯的数量）-1
for(int i=1;i<=m;i++)
{
p[a]+=bin[b];p[b]+=bin[a];
//p[i]表示第i盏等状态改变时，受影响的灯。
//如 0 1 1 0 0，这个二进制串其中的1表示，第i盏灯状态改变受影响的灯。
//为何是+，而不是赋值呢，是由于若是当前二进制串为0 0 1 0，1表示改变a灯状态受影响的灯。
//当又有灯与a相连时，如c灯 0 1 0 0 ，相加 后的串 0 1 1 0,表示与a的状态有关的灯。
}
for(int i=1;i<=n;i++)p[i]+=bin[i];//表示第i盏灯会影响本身。
cnt=n/2;dfs(1,0,0);//折半搜索。
flag=1;//表示搜的前一半仍是后一半。
cnt=n;dfs(n/2+1,0,0);
printf("%d\n",mn);
return 0;
}```