首页 > 代码库 > Uva1624 Knots
Uva1624 Knots
极其鬼畜的题。
初见根本没有思路。
二见根本没有思路。
……
多年(并不)之后突然想到,也许可以用链表模拟。
先用链表把每一个节点串起来,并对有覆盖的地方进行标记。
模拟解锁操作,如果一个节点和它所覆盖的节点之间没有其他结,那么进行逆self loop操作。
同理进行逆passing操作。
如果能把所有的结都解开,则答案是有解。
优化:把没有覆盖/被覆盖的节点提前删掉,缩短链表长度。
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 }
Uva1624 Knots
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。