CF776D The Door Problem
题目描述
Moriarty 把n个人分别困在酒店的n个不同房间里。一些房间的门是锁着的，另外一些是开着的。但是，有一个条件，只有当所有房间的门同时都是打开的时候，这些人才能逃脱。酒店里有m个开关。每个开关可以控制一些房间的门，但每扇门恰好被两个开关控制。
你得到了门的初始状态。每当你切换一个开关时（即打开变关闭，或关闭变打开），该开关所控制的所有房门的状态都会发生改变。例如，假设你切换了开关1，它连接的分别为房间1、2和3，这些房间门当前分别为锁着、开着、开着。那么，切换后，这三扇门会分别变为：开着、锁着、锁着。
你需要告诉 Sherlock，是否存在一种切换开关的方式，使得所有门同时都被打开。
输入格式
输入的第一行包含两个整数n和m$（2 \le n \le 10^{5}，2 \le m \le 10^{5}）$，分别表示房间数和开关数。
第二行包含n个用空格分隔的整数$r_{1}, r_{2}, …, r_{n}（0 \le r_{i} \le 1）$，表示每个房间门的当前状态。如果$r_{i}=0$，则第i个房间门是锁着的；否则是开着的。
接下来的m行，第i行包含一个整数$x_{i}（0 \le x_{i} \le n）$，接着是$x_{i}$个不重复的整数，分别表示第i个开关控制的房间数量以及各个被控制的房间编号。保证房间编号范围在1到n之间。保证每扇门恰好被两个不同的开关控制。
输出格式
如果存在一种切换开关的方式可以同时打开所有房门，则输出 “YES”（不含引号），否则输出 “NO”。
输入输出样例 #1
输入 #1
3 3
1 0 1
2 1 3
2 1 2
2 2 3
输出 #1
NO
输入输出样例 #2
输入 #2
3 3
1 0 1
3 1 2 3
1 2
2 1 3
输出 #2
YES
输入输出样例 #3
输入 #3
3 3
1 0 1
3 1 2 3
2 1 2
1 3
输出 #3
NO
说明/提示
在第二个输入样例中，各房门初始状态为[1,0,1]（0表示锁着，1表示开着）。
第一次切换第3个开关后，状态变为[0,0,0]，表示所有门都被锁住了。
然后再切换第1个开关，状态变为[1,1,1]，即所有房门都打开。
可以发现，对于第一个和第三个样例输入，都不存在使所有门都打开的切换方式。
由 ChatGPT 5 翻译
思路
注意到每个门只能有两个开关，所以我们可以将每个门存储着哪些开关存储一下假设第 i 扇门由开关 a、b 控制，那么最终状态为：
$r_i⊕x_a⊕x_b$
我们要求最终状态为1：
$r_i⊕x_a⊕x_b=1$
移项得到：
$x_a⊕x_b=1−r_i$
因此：
- 当 $r_i=1$ 时，$x_a=x_b$，两个开关状态相同。
- 当 $r_i=0$ 时，$x_a≠x_b$，两个开关状态不同。
令边权：
$w=1−r_i$
那么每条边都要求：
$color[a]⊕color[b]=w$
color记录每个节点的颜色，如果这个节点已经染色说明他已经被访问过了，如果这个节点还没有染色，那么把这个节点视为新的连通块的起点，并给一个颜色，那么其他修改后的节点颜色应该满足边上的“相同或不同”约束，如果不一致就是NO，如果都符合就是YES
代码
//Sunshine sunshine ladybugs awake,
//Clap your hooves and do a little shack.
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
using PII=pair<int,int> ;
const int MAXN=300005;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3f;
void solve(){
int n,m;
cin>>n>>m;
vector<int> r(n+1);
for(int i=1;i<=n;i++)cin>>r[i];
vector<vector<int>> controlledBy(n+1);
for(int i=1;i<=m;i++){
int q;cin>>q;
while(q--){
int x;cin>>x;
controlledBy[x].push_back(i);
}
}
vector<vector<PII>> graph(m+1);
for(int i=1;i<=n;i++){
int a=controlledBy[i][0];
int b=controlledBy[i][1];
int w=1-r[i];
graph[a].push_back({b,w});
graph[b].push_back({a,w});
}
vector<int> color(m+1,-1);
for(int start=1;start<=m;start++){
if(color[start]!=-1){
continue;
}
color[start]=0;
queue<int> q;
q.push(start);
while(!q.empty()){
int u=q.front();
q.pop();
for(auto [v,w]:graph[u]){
int expected_color=color[u]^w;
if(color[v]==-1){
color[v]=expected_color;
q.push(v);
}else if(color[v]!=expected_color){
cout<<"NO"<<endl;
return ;
}
}
}
}
cout<<"YES"<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
//int t;cin>>t;while(t--)
solve();
return 0;
}
