首页 / 更多教程 / CodeForces 776D The Door Problem【并查集】

CodeForces 776D The Door Problem【并查集】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeForces 776D The Door Problem【并查集】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1501字，纯文字阅读大概需要3分钟。

内容图文

CodeForces 776D The Door Problem【并查集】
并查集
设 f 1--m 表示 开的情况 m+1--2*m 表示关的情况
对于每盏灯
如果他 是关的 则 x--y x+m--y+m 表示要同关 或者同开
如果他 是开的 则 x+m--y x--y+m 表示一个关 一个开
如果一盏灯 的 x 连向 了 x+m 则表示是矛盾了 那么久是错误的

题意：给你n个门，和m组开关，每扇门都有两个开关控制，每个开关控制x扇门，
如果选择了某组开关，则使这组开关里的每个开关控制的所有的门按状态取反，
问你是否能使得所有的门状态为1
解析：将每个开关拆分成两个点，选这个开关和不选这个开关（x,x+m），根据每扇门的状态来，
如果状态为1，则需要同时选择这两个开关或者不选，如果状态为零，那么只能选择一个开关。
根据上面的情况做并查集，然后判断第i（选）组开关和i+m（选）是否联通，有则无解

 

             1 #include <cstdio>
 2usingnamespace std ; 
 3 4constint maxn = 100011 ; 
 5int n,m,k ; 
 6int light[ maxn ],g[maxn][3],f[maxn*2] ; 
 7 8 inline int getfather(int x) 
 9{
10if(x==f[x]) return x ; 
11     f[x] = getfather(f[x]) ; 
12return f[x] ; 
13}
1415 inline void merge(int x,int y) 
16{
17int xx,yy ; 
18     xx = getfather(x) ;   yy = getfather(y) ; 
19if(xx!=yy) f[xx] = yy ;  
20}
2122int main() 
23{
24     scanf("%d%d",&n,&m) ;    
25for(int i=1;i<=n;i++) 
26         scanf("%d",&light[ i ]) ; 
27int x,y ; 
28for(int i=1;i<=m;i++) 
29    {
30         scanf("%d",&k) ; 
31for(int j=1;j<=k;j++) 
32             scanf("%d",&x) , g[x][++g[x][0]] = i ;  
33    }
3435for(int i=1;i<=2*m;i++) f[ i ] = i ; 
36for(int i=1;i<=n;i++) 
37    {
38         x = g[i][1] ; 
39         y = g[i][2] ; 
40if(light[ i ]) 
41        {
42            merge(x,y) ; 
43             merge(x+m,y+m) ; 
44        }
45else46        {
47             merge(x,y+m) ; 
48             merge(y,x+m) ; 
49        }
50    }
5152bool flag = 0 ;
53int xx,yy ;  
54for(int i=1;i<=m;i++) 
55    {
56         xx = getfather( i ) ; 
57         yy = getfather( i+m ) ;  
58if(xx==yy) flag = 1 ; 
59    }
60if(flag) 
61         printf("NO\n") ; 
62else63         printf("YES\n") ; 
64return0 ; 
65 }

 

原文：http://www.cnblogs.com/third2333/p/7111280.html

内容总结

以上是互联网集市为您收集整理的CodeForces 776D The Door Problem【并查集】全部内容，希望文章能够帮你解决CodeForces 776D The Door Problem【并查集】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1327176.html

来源：【匿名】