首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。