先將點平均分成兩份，對於第一份先暴力搜索出所有狀態（二進制表示），
然後將狀態排序、去重（保留按動次數最少的）；再對另一份進行暴力搜索，
每搜出一個狀態，算得一個與它組合（異或）後，燈全部亮的狀態，
在第一份的狀態中進行二分查找，並更新答案。復雜度:O(2^(n/2)*log(2^(n/2)))
[cpp]
<pre name="code" class="cpp">#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
long long lt[37],zt[140005];
int sa[140005],ud[140005],n,m,tot,ans;
void Init()
{
int i,x,y;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
lt[i]|=1LL<<(i-1);
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
lt[x]|=1LL<<(y-1);
lt[y]|=1LL<<(x-1);
}
}
void dfs1(int t,int used,long long now)
{
if (t>n/2)
{
zt[++tot]=now;
ud[tot]=used;
sa[tot]=tot;
return;
} www.2cto.com
dfs1(t+1,used,now);
dfs1(t+1,used+1,now^lt[t]);
}
void sort(int l,int r)
{
int i=l,j=r,x=sa[i+j>>1],y;
while (i<=j)
{
while (zt[x]>zt[sa[i]]||(zt[x]==zt[sa[i]]&&ud[x]>ud[sa[i]])) i++;
while (zt[x]<zt[sa[j]]||(zt[x]==zt[sa[j]]&&ud[x]<ud[sa[j]])) j--;
if (i<=j)
{
y=sa[i]; sa[i]=sa[j]; sa[j]=y;
i++; j--;
}
}
if (i<r) sort(i,r);
if (l<j) sort(l,j);
}
int find(long long x)
{
int l=1,r=tot,mid;
while (l<=r)
{
mid=l+r>>1;
if (zt[sa[mid]]<x) l=mid+1; else
if (zt[sa[mid]]>x) r=mid-1; else
return sa[mid];
}
return -1;
}
void dfs2(int t,int used,long long now)
{
if (t>n)
{
int p=find(now^((1LL<<n)-1));
if (p>0) ans=min(ans,used+ud[p]);
return;
}
dfs2(t+1,used,now);
dfs2(t+1,used+1,now^lt[t]);
}
void Work()
{
int i,j,k;
dfs1(1,0,0);
sort(1,tot);
zt[0]=-1;
for (i=1,k=0;i<=tot;i++)
if (zt[sa[i]]!=zt[sa[i-1]])
sa[++k]=sa[i];
tot=k; ans=214748364;
dfs2(n/2+1,0,0);
printf("%d\n",ans);
}
int main()
{
Init();
Work();
return 0;
}</pre><br>
<br>
<pre></pre>
<pre name="code" class="cpp"></pre>
