解法:上述底線部分就是此題的解題關鍵,我們可以很方便地用圖去模擬這個關聯狀態,頂點表示開關,邊表示門,由於邊的權值可以直接決定兩端開關的異同,若門為開,兩開關相同;若門為鎖,兩開關相異,於是我們可以在一個小連通圖上直接從一個頂點 v 開始嘗試開關的切換與否,其他開關的狀態可以隨之算出,多餘的邊則負責檢查兩端開關的狀態是否已經讓自己這個門變成開啟狀態。如果沒有邊不滿足,則這個小圖就合法;如果有至少一條邊不滿足,則 v 還有另外一種狀態還沒嘗試,如果這個相反的嘗試之後就沒有邊不滿足,這個小圖亦合法;如果這兩種嘗試都有邊無法滿足,則總是會有一道門被鎖住。這題的一個小陷阱 (?) 就是整個大圖可能會分成一些互不連通的小連通子圖,所以寫程式的時候要確保每個連通子圖都有嘗試到,忽略了這件事讓我吃了一次 WA。
#include<bits/stdc++.h>usingnamespacestd;intn,m;vector<int>doors[100001];vector<pair<int,bool>>adj[100001];boolvisited[100001],switched[100001];booldfs(intv,booli){if(visited[v])returni==switched[v];boolans=true;visited[v]=true;switched[v]=i;for(autoconst&pii:adj[v])ans&=dfs(pii.first,i^pii.second);returnans;}intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);// IO 優化
cin>>n>>m;for(inti=1;i<=n;i++){intt;cin>>t;doors[i].push_back(1-t);}for(inti=1;i<=m;i++){intt;cin>>t;for(intj=0;j<t;j++){intt;cin>>t;doors[t].push_back(i);}}for(inti=1;i<=n;i++){adj[doors[i][1]].push_back(pair<int,bool>(doors[i][2],(bool)doors[i][0]));adj[doors[i][2]].push_back(pair<int,bool>(doors[i][1],(bool)doors[i][0]));}// Note that the graph may not be connected, so we have to try each switch in one configuration.
for(inti=1;i<=m;i++){if(!visited[i]){if(!dfs(i,true)){memset(visited,false,sizeofvisited);if(!dfs(i,false)){cout<<"NO\n";return0;}}}}cout<<"YES\n";return0;}