백준1739 도로 정비하기

작성일 | In

문제 링크

  • http://icpc.me/1739

사용 알고리즘

  • 2-SAT

풀이

가로 방향 도로의 방향 중 하나는 0, 다른 하나는 1로 표현합시다.
세로 방향 도로도 뱡향 중 하나는 0, 다른 하나는 1로 표현합시다.
2-SAT 문제로 바뀌게 됩니다.

식을 정리하다보면 (A and B) or (C and D)와 같은 식이 나오게 될텐데,
(A or C) and (A or D) and (B or C) and (B or D)와 같이 4개의 CNF로 바꿔주면 2-SAT문제로 풀 수 있습니다.

전체 코드

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;

vector<int> g[4040];
vector<int> r[4040];
int n, m, k;

inline int inv(int x){
	if(x > 2000) return x - 2000;
	else return x + 2000;
}

void init(){
	for(int i=0; i<4040; i++) g[i].clear(), r[i].clear();
}

void addEdge(int s, int e){
	g[s].push_back(e); r[e].push_back(s);
}

int chk[4040];
vector<int> dfn;

void dfs(int v){
	chk[v] = 1;
	for(auto i : g[v]){
		if(chk[i]) continue;
		chk[i] = 1;
		dfs(i);
	}
	dfn.push_back(v);
}

void rdfs(int v, int c){
	chk[v] = c;
	for(auto i : r[v]){
		if(chk[i]) continue;
		rdfs(i, c);
	}
}

void scc(){
	memset(chk, 0, sizeof chk); dfn.clear();
	for(int i=0; i<4040; i++) if(!chk[i]) dfs(i);
	memset(chk, 0, sizeof chk);
	int pv = 0; reverse(dfn.begin(), dfn.end());
	for(auto i : dfn) if(!chk[i]) rdfs(i, ++pv);
}

void solve(){
	init();
	cin >> n >> m >> k;
	while(k--){
		int a, b, c, d; cin >> a >> b >> c >> d;
		int p, q, r, s;
		if(a == c && b == d) continue;
		b += 1000; d += 1000;

		if(a < c) p = b, q = d;
		else p = inv(b), q = inv(d);
		if(b < d) r = a, s = c;
		else r = inv(a), s = inv(c);
		if(a == c){
			addEdge(inv(r), s);
			addEdge(inv(s), r);
		}else if(b == d){
			addEdge(inv(p), q);
			addEdge(inv(q), p);
		}else{
			addEdge(inv(p), q); addEdge(inv(q), p);
			addEdge(inv(p), r); addEdge(inv(r), p);
			addEdge(inv(s), q); addEdge(inv(q), s);
			addEdge(inv(s), r); addEdge(inv(r), s);
		}
	}
	scc();
	for(int i=0; i<2000; i++){
		if(chk[i] == chk[inv(i)]){
			cout << "No\n"; return;
		}
	}
	cout << "Yes\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--) solve();
}