很久以前wzf出给我们的题目。。。
考虑加边，每次并查集加完只要并查集内联通就说明实际堵塞
不联通就说明实际联通
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include<cstdio> int n,k,ans=1,f[10000005]; int Find(int x){return x==f[x]?f[x]:f[x]=Find(f[x]);} void Union(int sa,int sb){if(sa>sb)f[sa]=sb;else f[sb]=sa;} int Get(int x,int y){if(x==n || y==n || x==0 || y==0)return 0;return (x-1)*n+y;} int main(){freopen("4423.in","r",stdin);freopen("4423.out","w",stdout);scanf("%d %d",&n,&k);for(int i=1;i<=n*n+n;i++)f[i]=i;while(k--){ int sa1,sb1,sa2,sb2; char w1[5],w2[5]; scanf("%d %d %s %d %d %s",&sa1,&sb1,w1,&sa2,&sb2,w2); if(ans==0){sa1=sa2;sb1=sb2;w1[0]=w2[0];} if(w1[0]=='N'){ if(Find(Get(sa1,sb1))!=Find(Get(sa1-1,sb1))){Union(Find(Get(sa1,sb1)),Find(Get(sa1-1,sb1)));ans=1;} else ans=0; } else { if(Find(Get(sa1,sb1))!=Find(Get(sa1,sb1-1))){Union(Find(Get(sa1,sb1)),Find(Get(sa1,sb1-1)));ans=1;} else ans=0; } if(ans)puts("TAK"); else puts("NIE");}return 0;} |
评论 (0)
