[백준 16915] 호텔 관리

문제

https://www.acmicpc.net/problem/16915

 

알고리즘

2-SAT

 

풀이

풀면서 이 문제와 굉장히 유사하다고 느꼈습니다. 각 방마다 스위치가 두 개가 있고, 방의 상태에 따라 다음과 같은 선택을 할 수 있습니다. 각 방마다 연결되어있는 스위치를 A, B라고 하겠습니다.

 

1. 만약 방의 초기상태가 켜져 있다면, A와 B 둘 다 눌러서 켜진 상태를 유지하거나 A와 B둘다 누르지 않습니다.

2. 방의 초기상태가 꺼진 상태라면, A를 눌렀을 땐 B를 누르지 않고 B를 눌렀을 땐 A를 누르지 않아 켜지도록 합니다.

 

위 두 문장은 And or And 관계로 표현가능하며 2-CNF형태를 만족시키도록 전개해주면 문제를 풀 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

#define T(x) (x<<1)
#define F(x) (x<<1|1)

int N, M,x,cnt,SC,VC;

vector<vector<int>> adj,rs; //room_to_switch rs[i] :i방과 연결된 스위치들
vector<int> discovered, sccid, room;
stack<int> st;

int scc(int here) {
    int ret = discovered[here] = VC++;
    st.emplace(here);

    for (auto there : adj[here]) {
        if (discovered[there] == -1) ret = min(ret, scc(there));
        else if (sccid[there] == -1) ret = min(ret, discovered[there]);
    }

    if (ret == discovered[here]) {
        while (1) {
            int t = st.top();st.pop();
            sccid[t] = SC;
            if (t == here) break;
        }
        ++SC;
    }
    return ret;
}

void OR(int u, int v) {
    adj[u ^ 1].emplace_back(v);
    adj[v ^ 1].emplace_back(u);
}

void AOA(int a, int b, int c, int d) {
    OR(a, c); OR(a, d);
    OR(b, c); OR(b, d);
}

int main() {
    FAST;
    cin >> N >> M;
    adj.resize(M << 1);
    rs.resize(N);
    room.resize(N);
    discovered = sccid = vector<int>(M << 1, -1);
    rep(i, N) cin >> room[i];
    rep(i, M) {
        cin >> cnt;
        while (cnt--) {
            cin >> x;
            rs[--x].emplace_back(i);
        }
    }

    rep(i, N) {
        int f = rs[i][0];
        int s = rs[i][1];
        if (room[i]) AOA(T(f), T(s), F(f), F(s));
        else AOA(T(f), F(s), F(f), T(s));
    }
    rep(i, M << 1) if (discovered[i] == -1) scc(i);

    bool flag = true;
    
    for (int i = 0;i < M << 1;i += 2) {
        int A = sccid[i];
        int B = sccid[i ^ 1];
        if (A == B) {
            flag = false;
            break;
        }
    }
    cout << flag;
    return 0;
}