📝 문제 정보#
🧐 관찰 및 접근#
- 모든 심사위원에 대해 (and) 각 심사위원별로 표 두개중 하나를 만족해야 한다. (or)
- 따라서 $(A \lor B) \land (C \lor D) \land \cdots$ 의 2-sat 문제로 변환 가능하다!
- 모델링만 잘 해보자.
- 가능한 변수의 개수 $= 1000 *2 = 2000$ 에 대해
- $i$ 번 참가자가 진출: $2*i$, 진출 실패: $2*i+1$로 모델링하자.
- 가능한 변수의 개수 $= 1000 *2 = 2000$ 에 대해
- 1번 참가자인 상근이는 무조건 통과해야 한다.
- $\neg x \to x$ 를 만족하면 되므로, $1 \to 0$을 추가하자.
💻 풀이#
- 코드 (C++):
void solve(){
int N, M;
while(cin >> N >> M){
DirectedGraph dg(2*N);
rep(i, 0, M){
int u, v; cin >> u >> v;
if(u > 0) u = 2*(u-1);
else u = 2*(-u-1)+1;
if(v > 0) v = 2*(v-1);
else v = 2*(-v-1)+1;
dg.add_2sat_edge(u, v);
}
dg.add_2sat_edge(0, 0);
cout << (dg.is2SAT() ? "yes\n" : "no\n");
}