백준 16367 TV Show Game

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

 

클래스7 다 밀기 중

 

3개 중 2개 이상 참이어야 한다..? 한참 동안 아무 생각도 안 들었다

각 전등을 부울 리터럴으로 생각할 수 있고, 부울식에서 우리가 풀 수 있는 건 2-SAT밖에 없으니 어케어케 2-CNF 꼴로 바꿔야 한다

A, B, C 중 2개 이상이 참임은 (A or B) and (B or C) and (C or A)와 동치이며, 이 식은 2-CNF 형식이니 문제를 풀 수 있다

 

이제 플로우 n개 SA 2개 풀어야하는데,, 상당히귀찮은

 

#include <bits/stdc++.h>
using namespace std;
 
vector<int> G[10101], rev[10101], stk;
int scc[10101];
 
void add(int a, int b){
    a = a > 0 ? a*2 : -a*2+1;
    b = b > 0 ? b*2 : -b*2+1;
    G[a^1].push_back(b);
    G[b^1].push_back(a);
    rev[b].push_back(a^1);
    rev[a].push_back(b^1);
}
 
void dfs(int v){
    scc[v] = -1;
    for (int i : G[v]){
        if (!scc[i])    
            dfs(i);
    }
    stk.push_back(v);
}
 
void get(int v, int c){
    scc[v] = c;
    for (int i : rev[v]){
        if (scc[i] == -1)
            get(i, c);
    }
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    int k, n;
    cin >> k >> n;
    for (int i = 0; i < n; i++){
        int a[3];
        char c;
        for (int j = 0; j < 3; j++) {
            cin >> a[j] >> c;
            if (c == 'R') a[j] = -a[j];
        }
        add(a[0], a[1]);
        add(a[1], a[2]);
        add(a[2], a[0]);
    }
    for (int i = 2; i <= k*2+1; i++){
        if (!scc[i])
            dfs(i);
    }
    reverse(stk.begin(), stk.end());
    int ii = 0;
    for (int i : stk){
        if (scc[i] == -1)
            get(i, ++ii);
    }
    string ans;
    for (int i = 1; i <= k; i++){
        if (scc[i*2] == scc[i*2+1]){
            cout << -1;
            return 0;
        }
        ans.push_back("RB"[scc[i*2] > scc[i*2+1]]);
    }
    cout << ans;
}