BZOJ 1770 [Usaco2009 Nov]lights 燈折半搜索

题目描述#

贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿，突然，牛棚的电源跳闸了，所有的灯都被关闭了。贝希是一个很胆小的女生，在伸手不见拇指的无尽的黑暗中，她感到惊恐，痛苦与绝望。她希望您能够帮帮她，把所有的灯都给重新开起来！她才能继续快乐地跟她的闺密们继续玩游戏！

牛棚中一共有N（1 <= N <= 35）盏灯，编号为1到N。这些灯被置于一个非常复杂的网络之中。有M（1 <= M <= 595）条很神奇的无向边，每条边连接两盏灯。每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候，这盏灯本身，还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是：当一盏灯是开着的时候，这盏灯被关掉；当一盏灯是关着的时候，这盏灯被打开。问最少要按下多少个开关，才能把所有的灯都给重新打开。数据保证至少有一种按开关的方案，使得所有的灯都被重新打开。

输入#

＊第一行：两个空格隔开的整数：N和M。

＊第二到第M+1行：每一行有两个由空格隔开的整数，表示两盏灯被一条无向边连接在一起。没有一条边会出现两次。

输出#

第一行：一个单独的整数，表示要把所有的灯都打开时，最少需要按下的开关的数目。

样例输入#

輸入細節：

一共有五盞燈。燈1、燈4和燈5都連接著燈2和燈3。

样例输出#

1
3

輸出細節：

按下在燈1、燈4和燈5上面的開關。

题解#

【折半搜索】
将需要搜索的元素分为不关联的两个部分，分别搜索

在本题中 N的范围有35如果直接搜的话 $2^35$ 会T的很惨
所以我们将N分为前后两部分
现将前mid个搜出来，记录每个状态集合的最小的答案
之后出来后mid + 1到n搜完后加上他的补集跟新答案

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
#include <map>
5
using namespace std;
6
long long A[36], full, bin[37];
7
int Min = 0x3f, n, m;
8
map<long long, int> Mp;
9
void dfs1(int x, long long now, int k)
10
{
11
  if(x == m + 1)
12
  {
13
    if(now == full)
14
      Min = min(k, Min);
15
    int t = Mp[now];
16
    if(!t || t > k)
17
      Mp[now] = k;
18
    return;
19
  }
20
  dfs1(x + 1, now, k);
21
  dfs1(x + 1, now^A[x], k + 1);
22
}
23
void dfs2(int x, long long now, int k)
24
{
25
  if(x == n + 1)
26
  {
27
    if(now == full)
28
      Min = min(k, Min);
29
    int t = Mp[full - now];
30
    if(!t)
31
      return;
32
    Min = min(t + k, Min);
33
    return;
34
  }
35
  dfs2(x + 1, now, k);
36
  dfs2(x + 1, now^A[x], k + 1);
37
}
38
int main()
39
{
40
  // freopen("lights.in","r",stdin);
41
  // freopen("lights.out","w",stdout);
42
  int c;
43
  scanf("%d%d", &n, &c);
44
  bin[1] = 1;
45
  for (int i = 2; i < 37; i++)
46
    bin[i] = bin[i - 1] << 1;
47
  int a, b;
48
  for (int i = 1; i <= c; i++)
49
  {
50
    scanf("%d%d", &a, &b);
51
    A[a] += bin[b];
52
    A[b] += bin[a];
53
  }
54
  for (int i = 1; i <= n; i++)
55
    A[i] += bin[i];
56
  full = bin[n + 1] - 1;
57
  m = n >> 1;
58
  dfs1(1, 0, 0);
59
  dfs2(m + 1, 0, 0);
60
  printf("%d", Min);
61
}