776-D. The Door Problem

Tags: graph

出處:https://codeforces.com/contest/776/problem/D
提交:https://codeforces.com/contest/776/submission/111162737

問題:給定 $n\in[2,10^5]$ 道門和 $m\in[2,10^5]$ 個開關,每道門有各自的上鎖狀態,而每個開關可以各自控制任意數量 $[0,n]$ 的門,每個開關一切換就會讓所有自己掌管的門由鎖轉開或由開變鎖,每個開關可以選擇切換與否。那現在保證每個門恰好都會被兩個開關所控制,請問有沒有辦法讓所有的門都變成開啟狀態?

解法:上述底線部分就是此題的解題關鍵,我們可以很方便地用圖去模擬這個關聯狀態,頂點表示開關,邊表示門,由於邊的權值可以直接決定兩端開關的異同,若門為開,兩開關相同;若門為鎖,兩開關相異,於是我們可以在一個小連通圖上直接從一個頂點 v 開始嘗試開關的切換與否,其他開關的狀態可以隨之算出,多餘的邊則負責檢查兩端開關的狀態是否已經讓自己這個門變成開啟狀態。如果沒有邊不滿足,則這個小圖就合法;如果有至少一條邊不滿足,則 v 還有另外一種狀態還沒嘗試,如果這個相反的嘗試之後就沒有邊不滿足,這個小圖亦合法;如果這兩種嘗試都有邊無法滿足,則總是會有一道門被鎖住。這題的一個小陷阱 (?) 就是整個大圖可能會分成一些互不連通的小連通子圖,所以寫程式的時候要確保每個連通子圖都有嘗試到,忽略了這件事讓我吃了一次 WA。

實作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> doors[100001];
vector<pair<int, bool>> adj[100001];
bool visited[100001], switched[100001];

bool dfs(int v, bool i) {
    if (visited[v]) return i == switched[v];
    bool ans = true; visited[v] = true; switched[v] = i;
    for (auto const &pii: adj[v])
        ans &= dfs(pii.first, i ^ pii.second);
    return ans;
}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        int t; cin >> t;
        doors[i].push_back(1-t);
    }
    for (int i=1; i<=m; i++) {
        int t; cin >> t;
        for (int j=0; j<t; j++) {
            int t; cin >> t;
            doors[t].push_back(i);
        }
    }
    for (int i=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 (int i=1; i<=m; i++) {
        if (!visited[i]) {
            if (!dfs(i, true)) {
                memset(visited, false, sizeof visited);
                if (!dfs(i, false)) {
                    cout << "NO\n";
                    return 0;
                }
            }
        }
    }
    cout << "YES\n";
    return 0;
}

結果: Example image