題目鏈接：這里 題意:有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;}新聞熱點
疑難解答
