首页 > 代码库 > Uva11464 Even Parity

Uva11464 Even Parity

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

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

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

 

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<list> 8 using namespace std; 9 int read(){10     int x=0,f=1;char ch=getchar();11     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();}12     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();}13     return x*f;14 }15 struct node{16     int pre,nxt;17 }a[1000010];18 int link[1000010];19 int ud[1000010];20 int L,P;21 void Del(int x){22     ud[x]=0;23     a[a[x].pre].nxt=a[x].nxt;24     a[a[x].nxt].pre=a[x].pre;25 }26 int T;27 int main(){28     T=read();29     int L,P,i,j;30     for(int cas=1;cas<=T;cas++){31         memset(link,0,sizeof link);32         memset(ud,0,sizeof ud);33         L=read();P=read();34         for(i=0;i<L;i++){35             a[i].pre=i-1;36             a[i].nxt=i+1;37         }38         a[0].pre=L-1;a[L-1].nxt=0;39         int u,v;40         for(i=1;i<=P;i++){41             u=read();v=read();42             link[u]=v;link[v]=u;43             ud[u]=1;ud[v]=-1;//???? 44         }45         for(i=0;i<L;i++)if(!ud[i])Del(i);46         int hd=0;47         while(P){48             bool flag=1;49             while(!ud[hd])hd++;50             for(i=a[hd].nxt; i!=hd && flag; i=a[i].nxt){51                 int u=i,v=a[i].nxt;52                 if(ud[u]==ud[v] && (a[link[u]].nxt==link[v] ||53                     a[link[v]].nxt==link[u])){54                         Del(u);    Del(v);55                         Del(link[u]);56                         Del(link[v]);57                         P-=2;58                         flag=0;59                     }60                 //passing61                 else if(link[v]==u || link[u]==v){62                     Del(u);Del(v);63                     P--;64                     flag=0;65                 }66                 //selfloop67             }68             if(flag)break;69         }70         printf("Case #%d: ",cas);71         if(!P)printf("YES\n");72         else printf("NO\n");73     }74     return 0;75 }

 

Uva11464 Even Parity