Uva11464 Even Parity

枚举每个格子的状态显然是不可能的。

思考发现，矩阵第一行的状态确定以后，下面的状态都可以递推出来。

于是状压枚举第一行的状态，递推全图的状态并判定是否可行。

 /*by SilverN*/

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<list>

 using namespace std;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct node{

     int pre,nxt;

 }a[];

 int link[];

 int ud[];

 int L,P;

 void Del(int x){

     ud[x]=;

     a[a[x].pre].nxt=a[x].nxt;

     a[a[x].nxt].pre=a[x].pre;

 }

 int T;

 int main(){

     T=read();

     int L,P,i,j;

     for(int cas=;cas<=T;cas++){

         memset(link,,sizeof link);

         memset(ud,,sizeof ud);

         L=read();P=read();

         for(i=;i<L;i++){

             a[i].pre=i-;

             a[i].nxt=i+;

         }

         a[].pre=L-;a[L-].nxt=;

         int u,v;

         for(i=;i<=P;i++){

             u=read();v=read();

             link[u]=v;link[v]=u;

             ud[u]=;ud[v]=-;//????

         }

         for(i=;i<L;i++)if(!ud[i])Del(i);

         int hd=;

         while(P){

             bool flag=;

             while(!ud[hd])hd++;

             for(i=a[hd].nxt; i!=hd && flag; i=a[i].nxt){

                 int u=i,v=a[i].nxt;

                 if(ud[u]==ud[v] && (a[link[u]].nxt==link[v] ||

                     a[link[v]].nxt==link[u])){

                         Del(u);    Del(v);

                         Del(link[u]);

                         Del(link[v]);

                         P-=;

                         flag=;

                     }

                 //passing

                 else if(link[v]==u || link[u]==v){

                     Del(u);Del(v);

                     P--;

                     flag=;

                 }

                 //selfloop

             }

             if(flag)break;

         }

         printf("Case #%d: ",cas);

         if(!P)printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }