解題區►解題區 - UVa

UVa 12745 - Wishmaster

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有 n 個地點，每個地點要不用高架橋、要不使用地下化道路兩種方式，每個民眾有兩個願望，分別希望哪裡以什麼方式建造，只要滿足每一個民眾的其中一種願望即可。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
2
3 5
-1 2
1 3
3 -2
1 -3
-2 -3
4 4
-1 2
1 3
-2 4
-3 -4

Sample Output

1
2
Case 1: No
Case 2: Yes

Solution

一道樸素的 2-SAT 問題。

建圖，利用 SCC 將點縮起來，形成 DAG 圖。

如果 val 與 !val 被縮在同一個點，即為矛盾。
當關係為 (a or b) and (c or !d) and …

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
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXN 262144
vector<int> g[MAXN];
int vfind[MAXN], findIdx;
int stk[MAXN], stkIdx;
int in_stk[MAXN], visited[MAXN];
int contract[MAXN];
int scc_cnt;
int scc(int nd) {
    in_stk[nd] = visited[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd];
    for(int i = 0; i < g[nd].size(); i++) {
        if(!visited[g[nd][i]])
            mn = min(mn, scc(g[nd][i]));
        if(in_stk[g[nd][i]])
            mn = min(mn, vfind[g[nd][i]]);
    }
    if(mn == vfind[nd]) {
        do {
            in_stk[stk[stkIdx]] = 0;
            contract[stk[stkIdx]] = nd;
        } while(stk[stkIdx--] != nd);
        scc_cnt++;
    }
    return mn;
}
int main() {
    int testcase, n, m, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        n = (n + 1)* 2;
        for(int i = 0; i < n; i++)
            g[i].clear();
        // 2*node: false, 2*node+1: true
        while(m--) {
        	int a, b, x, y;
        	scanf("%d %d", &a, &b);
        	x = abs(a), y = abs(b);
        	x <<= 1, y <<= 1;
        	if (a < 0)	x ^= 1;
        	if (b < 0)	y ^= 1;
        	g[x^1].push_back(y);
        	g[y^1].push_back(x);
        }
        //SCC
        memset(visited, 0, sizeof(visited));
        memset(in_stk, 0, sizeof(in_stk));
        scc_cnt = 1;
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                stkIdx = 0;
                findIdx = 0;
                scc(i);
            }
        }
        //2-SAT check
        int hasSol = 1;
        for(int i = 0; i < n && hasSol; i+=2)
            if(contract[i] == contract[i^1])
                hasSol = 0;
            
        printf("Case %d: %s\n", ++cases, hasSol ? "Yes" : "No");
    }
    return 0;
}
/*
2
3 5
-1 2
1 3
3 -2
1 -3
-2 -3
4 4
-1 2
1 3
-2 4
-3 -4
*/