NOJ 1610 - c++编程基础 - 编程开发网

先将点平均分成两份，对于第一份先暴力搜索出所有状态（二进制表示），
然后将状态排序、去重（保留按动次数最少的）；再对另一份进行暴力搜索，
每搜出一个状态，算得一个与它组合（异或）后，灯全部亮的状态，
在第一份的状态中进行二分查找，并更新答案。复杂度:O(2^(n/2)*log(2^(n/2)))
[cpp]

#include  
 
 #include  
 
 #include  
 
 #include  
 
 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]         if (i<=j) 
 
         { 
 
             y=sa[i]; sa[i]=sa[j]; sa[j]=y; 
 
             i++; j--; 
 
         } 
 
     } 
 





     if (i     if (l } 
 
  
 
 int find(long long x) 
 
 { 
 
     int l=1,r=tot,mid; 
 
     while (l<=r) 
 
     { 
 
         mid=l+r>>1; 
 
         if (zt[sa[mid]]         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<         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; 
 
 }