USACO NOV09 Lights

由于灯的上限是35个，因此可以用一个64位整型表示整个状态，二进制1表示灯亮，0表示灯灭。那么，初始状态就是0,目标状态(target)就是(1 << N)-1.
同样，也可以把每个开关改变的灯记录在一个64位整型数组op里，按下开关i后的新状态就等于当前状态xor op[i].

由于xor具有自反性和交换性，因此无需考虑按开关的顺序，每个开关也最多只按一次，否则效果就抵消了。因此很容易写出下面的搜索函数：

C语言: 高亮代码由发芽网提供

void dfs(unsigned long long s,int p,int i)
{
   if(success)     return;
   if(p == depth)        //p表示按下开关的数量
   {
       if(s == target)      success = 1;
       return;
   }
   if(i == N)
       return;
   dfs(s,p,i + 1);   //不按开关
   dfs(s ^ op[i],p + 1,i + 1);     //按开关
}

依次增加depth，并运行dfs(0,0,0)，直到success为真，此时的depth就是答案。不过，这个DFS的复杂度是2^N方的，在N=20以下都可以迅速出解，当N=30时就严重超时了。

如何降低复杂度呢？我们要寻找的是一个满足0 xor op[t1] xor op[t2] xor .... xor op[tk] = target的序列，根据xor的交换律和结合律，我们可以把这个序列分成两半求解。本题的关键就在这里。



对前面一半的灯，可以采用DFS获得所有可能的状态，把这些状态保存在散列表中（如果有重复状态，选择按下开关数最少的）。

对于后一半的灯，同样使用DFS获得所有可能的状态，对于得到的状态S，在散列表中寻找H，满足S xor H = target，根据xor的性质，可直接在散列表中查找target xor S是否存在。若存在，则判断是否更新答案。

这个算法DFS的深度是第一个算法的一半，极限情况下只会DFS到第18层。所有数据均可在0.1s内出解。

需格外注意的是，C中整数的默认存储类型是long，因此1左移35获得的是0,要先把1强制转换成64为再左移。

代码如下：

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 40
#define TABLESIZE 1048576

struct node
{
   unsigned long long s;
   int ch;
   struct node *next;
}*table[TABLESIZE] = {};

typedef struct node node;

int N,M;
int half;
unsigned long long op[MAXN];
unsigned long long target;
unsigned long long one = (unsigned long long)1;
int ans = MAXN;

void init()
{
   scanf("%d%d",&N,&M);
   int i,a,b;
   for(i = 0;i < N;i ++)
       op[i] = one << i;  //!!!!NOTICE!!!!
   for(i = 0;i < M;i ++)
   {
       scanf("%d%d",&a,&b);
       a --;b --;
       op[a] = op[a] | (one << b);
       op[b] = op[b] | (one << a);
   }
   if(N == 1)
   {
       printf("1\n");
       fclose(stdout);
       exit(0);
   }
}

node *find(unsigned long long s)   //查找散列表
{
   unsigned long h = (unsigned long)(s & 0xFFFFF);
   node *p;
   for(p = table[h];p != NULL;p = p->next)
       if(p->s == s)    return p;
   return NULL;
}

void record(unsigned long long s,int ch)   //记录新的状态
{
   node *p;
   p = find(s);
   if(p == NULL)
   {
       unsigned long h = (unsigned long)(s & 0xFFFFF);
       p = malloc(sizeof(node));
       p->s = s;
       p->next = table[h];
       p->ch = ch;
       table[h] = p;
       return;
   }
   if(p->ch > ch)
       p->ch = ch;
}

void check(unsigned long long s,int ch)
{
   node *p;
   p = find(target ^ s);
   if(p != NULL && p->ch + ch < ans)
       ans = p->ch + ch;
}

void dfs(unsigned long long s,int p,int i)   //处理前面一半的灯
{
   if(i == half)
   {
       record(s,p);
       return;
   }
   dfs(s,p,i + 1);
   dfs(s ^ op[i],p + 1,i + 1);
}

void dfs2(unsigned long long s,int p,int i)    //处理后一半灯
{
   if(i == N)
   {
       check(s,p);
       return;
   }
   dfs2(s,p,i + 1);
   dfs2(s ^ op[i],p + 1,i + 1);
}

int main()
{
   freopen("lights.in","r",stdin);
   freopen("lights.out","w",stdout);
   init();
   target = (one << N) - 1;   //!!!!NOTICE!!!!
   half = N / 2;
   dfs(0,0,0);
   dfs2(0,0,half);
   printf("%d\n",ans);
   fclose(stdout);
   fclose(stdin);
   return 0;
}