首页 > 代码库 > Codeforces Round #400 D. The Door Problem(2-sat)

Codeforces Round #400 D. The Door Problem(2-sat)

2024-09-05 23:35:44   217人阅读

题目链接：Codeforces Round #400 D. The Door Problem

题意：

有n扇门，每扇门有个初始状态，并且受两个开关控制。

现在给你m个开关控制门的信息，每个开关能将它所控制的门的状态翻转。

问能不能通过一定操作，将所以的门的状态都处于开的情况。

题解：

这题用2sat,也可以用并查集判断联通块。这里我用2sat。

因为一个开关可以控制多扇门，而每个门只由两个开关控制，所以这里我们考虑对这m个开关建图。

如果这扇门的状态为1，那么要让它保持1的状态，我们只能同时按下控制它的两个开关或者两个都不按。

如果这扇门的状态为0，那么我们必须按并且只能按其中一个控制这扇门的开关。

然后根据这个建图。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=a;i<=b;++i)
 4 using namespace std;
 5 const int N=1e5+7;
 6 namespace Twosat
 7 {
 8     int q[N*4],t,n,g[N*2],v[N*4],nxt[N*4],ed;bool vis[N*2];
 9     void init(int _n){n=_n,mst(g,0),mst(vis,0),ed=0;}
10     void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
11     bool dfs(int x){
12         if(vis[x>n?x-n:x+n])return 0;
13         if(vis[x])return 1;
14         vis[q[++t]=x]=1;
15         for(int i=g[x];i;i=nxt[i])if(!dfs(v[i]))return 0;
16         return 1;
17     }
18     bool solve(){
19         F(i,1,n)if(!vis[i]&&!vis[i+n]){
20             t=0;
21             if(!dfs(i)){
22                 while(t)vis[q[t--]]=0;
23                 if(!dfs(i+n))return 0;
24             }
25         }
26         return 1;
27     }
28 }
29 int n,m,a[N],t,u,v,x;
30 
31 vector<int>q[N];
32 
33 int main(){
34     scanf("%d%d",&n,&m);
35     Twosat::init(m);
36     F(i,1,n)scanf("%d",a+i);
37     F(i,1,m)
38     {
39         scanf("%d",&t);
40         while(t--)
41         {
42             scanf("%d",&x);
43             q[x].push_back(i);
44         }
45     }
46     F(i,1,n)
47     {
48         int u=q[i][0],v=q[i][1];
49         if(a[i])
50         {
51             Twosat::adg(u+m,v+m),Twosat::adg(v+m,u+m);
52             Twosat::adg(u,v),Twosat::adg(v,u);
53         }
54         else {
55             Twosat::adg(u+m,v),Twosat::adg(v,u+m);
56             Twosat::adg(u,v+m),Twosat::adg(v+m,u);
57         }
58     }
59     Twosat::solve()?puts("YES"):puts("NO");   
60     return 0; 
61 }
View Code

 

Codeforces Round #400 D. The Door Problem(2-sat)


联系
我们