Bzoj 1823(2-SAT)

BZOJ 1823
经典2-SAT模型,注意输入

Tarjan版本:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int tb, n, m, belongs[2 * 100 + 5], vis[2 * 100 + 5], scc_num, dfn[2 * 100 + 5], low[2 * 100 + 5];
vector<int> G[2 * 100 + 5];//2x->m 2x+1->h
stack<int> s;
void tarjan(int u) {
dfn[u] = low[u] = ++tb, vis[u] = -1, s.push(u);
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (vis[v] == 0) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v] == -1) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
int e;
scc_num++;
do {
e = s.top(); s.pop();
belongs[e] = scc_num;
vis[e] = 1;
} while (e != u);
}
}
int getss()
{
char ans;
while (true) {
ans = getchar();
if (ans == 'm') return 0;
if (ans == 'h') return 1;
int ret = 0;
while (ans >= '0' && ans <= '9') {
ret = ret * 10 + ans - '0';
ans = getchar();
}
if (ret > 0) return ret;
}
}
void clean() {
tb = scc_num = 0;
for (int i = 0; i <= 2 * 100 + 1; i++) dfn[i] = low[i] = belongs[i] = vis[i] = 0, G[i].clear();
}
void solve() {
scanf("%d%d", &n, &m);
clean();
char c1, c2;
int a1, a2;
for (int i = 1; i <= m; i++) {
c1 = getss(), a1 = getss(), c2 = getss(), a2 = getss();
int x = 2 * (a1 - 1) + (c1 == 1) , y = 2 * (a2 - 1) + (c2 == 1);
G[x].push_back(y ^ 1), G[y].push_back(x ^ 1);
}
for (int i = 1; i <= n * 2; i++) if (!vis[i]) tarjan(i);
for (int i = 1; i <= 2 * n; i += 2) {
if (belongs[i] == belongs[i ^ 1]) {
printf("BAD\n");
return ;
}
}
printf("GOOD\n");
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}

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
90
91
92
93
94
95
96
97
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXN = 100 + 5;
struct twoSAT
{
bool mark[MAXN*2];
vector<int> G[MAXN*2];
int n;
int c, S[MAXN*2];
void init(int ni)
{
n = ni;
for (int i=0;i<2*n;i++) G[i].clear();
ms(mark, false);
}
bool dfs(int x)
{
if (mark[x^1]) return false;
if (mark[x]) return true;
mark[x] = true;
S[++c] = x;
for (int i=0;i<G[x].size();i++)
if (!dfs(G[x][i])) return false;
return true;
}
void addE(int x, int y, int xv, int yv)
{
x = x * 2 + xv;
y = y * 2 + yv;
G[x^1].push_back(y);
G[y^1].push_back(x);//2x for man, 2x+1 for han
}
bool solve()
{
for (int i=0;i<2*n;i+=2)
if (!mark[i] && !mark[i+1])
{
c = 0;
if (!dfs(i))
{
for (int j=1;j<=c;j++) mark[S[j]] = false;
c = 0;
if (!dfs(i+1)) return false;
}
}
return true;
}
}ts;
int k;
int n,m;
int getss()
{
char ans;
while (true)
{
ans = getchar();
if (ans=='m') return 0;
if (ans=='h') return 1;
int ret = 0;
while (ans>='0'&&ans<='9')
{
ret = ret*10+ans-'0';
ans = getchar();
}
if (ret>0) return ret;
}
}
void inpu()
{
int v1 = getss();
int z1 = getss();
int v2 = getss();
int z2 = getss();
ts.addE(z1-1, z2-1, v1, v2);
}
int main()
{
scanf("%d", &k);
while (k--)
{
scanf("%d%d", &n,&m);
ts.init(n);
for (int i=0;i<m;i++)
{
inpu();
}
if (ts.solve())
{
printf("GOOD\n");
} else printf("BAD\n");
}
return 0;
}
------ 本文结束 ------