题目链接：这里 题意:有n道门，m个开关，每道门由m个开关中的两个控制，若门的状态是0(关)，那么改变控制这道门的一个开关之后，门的 状态就变为1(开)，若门的状态是1(开)，那么改变控制这道门的一个开关之后，门的状态就变为0(关)。 现已知n道门的初始状态，以及m个开关分别控制哪些门，问能不能通过按下某些开关，使得全部门的状态都变为1。 解法：看到每道门恰好两个开关控制，想到2-SAT解决。对于每道门，已知控制这道门的开关是x,y，如果这道门的初始状态为1，那么需要控制它的开关同时为1或者同时开关，相反如果这道门的初始状态为0,那么需要控制它的开关一个开一个关。所以按照这个逻辑建边跑TwoSAT就可以了。这也是我写的第一个TwoSAT，模板是白书模板，感觉也不错的。
#include <bits/stdc++.h>using namespace std;const int maxn = 1e5+5;int door[maxn];vector <int> v[maxn];struct TwoSAT{ int n; vector <int> G[maxn*2]; bool mark[maxn*2]; int S[maxn*2], c; bool dfs(int x){ if(mark[x^1]) return false; if(mark[x]) return true; mark[x] = true; S[c++] = x; for(int i = 0; i < G[x].size(); i++){ if(!dfs(G[x][i])) return false; } return true; } void init(int n){ this->n = n; for(int i = 0; i < n*2; i++) G[i].clear(); memset(mark, 0, sizeof(mark)); } void addedge(int x, int xval, int y, int yval){ x = x * 2 + xval; y = y * 2 + yval; G[x^1].push_back(y); G[y^1].push_back(x); } bool solve(){ for(int i = 0; i < 2*n; i += 2) if(!mark[i] && !mark[i+1]){ c = 0; if(!dfs(i)){//已经尝试过把i标记为true，然而不行，那么在尝试将i+1标记为真时，先把i的影响消掉 while(c > 0) mark[S[--c]] = false; if(!dfs(i + 1)) return false; } } return true; }}twosat;int main(){ int n, m, x, y; cin >> n >> m; for(int i = 0; i < n; i++){ scanf("%d", &door[i]);} for(int i = 0; i < m; i++){ scanf("%d", &x); for(int j = 0; j < x; j++){ scanf("%d", &y); v[y - 1].push_back(i); } } twosat.init(m); for(int i = 0; i < n; i++){ if(door[i]){ twosat.addedge(v[i][0], 0, v[i][1], 1); twosat.addedge(v[i][0], 1, v[i][1], 0); } else{ twosat.addedge(v[i][0], 0, v[i][1], 0); twosat.addedge(v[i][0], 1, v[i][1], 1); } } puts(twosat.solve() ? "YES" : "NO"); return 0;}新闻热点
疑难解答
