hdu 1824 Let's go home

本文从WordPress迁移而来, 查看全部WordPress迁移文章

2-sat判定

题意:虽然是中文题,但是很多歧义,构图容易搞不清,所以说一下。a表示a回家,~a表示a留下

  1. 队长回家的话,两个队友一定要留下,必然关系,a->~b,a->~c
  2. 只要一个队员回家了队长都要留下,必然关系,b->~a,c->~a
  3. 一对队员的话,a留下b必回家,b留下a必回家。~a->b,~b->a但是反过来则不是。a回家,没说b一定要留下,同样b回家没说a一定要留下,不要加这两条边.意思就是一定至少有一个人要回家
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 6010 //1000队,3000人,每个人拆成两点,6000点,a回家,~a留下
#define M 5010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n;
vector<int>e[N];
int dfn[N],low[N],stack[N],belong[N],dcnt,bcnt,top;
bool ins[N];

inline void add(int u ,int v){
e[u].pb(v);
}

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u; ins[u] = true;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(ins[v])
low[u] = min(low[u],dfn[v]);
}
if(dfn[u] == low[u]){
++bcnt;
while(true){
int x = stack[top--];
ins[x] = false;
belong[x] = bcnt;
if(x == u) break;
}
}
}

bool check(){
dcnt = bcnt = top = 0;
cl(dfn,0);
cl(ins,false);
for(int i = 0; i < 2*n; i++)
if(!dfn[i])
tarjan(i);
for(int i = 0; i < n; i++)
if(belong[i<<1] == belong[i<<1|1])
return false;
return true;
}

int main(){
int t,p;
while(scanf("%d%d",&t,&p)!=EOF){
n = 3*t;
for(int i = 0; i < 2*n; i++)
e[i].clear();
for(int i = 0; i < t; i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x<<1,y<<1|1); add(x<<1,z<<1|1);
add(y<<1,x<<1|1); add(z<<1,x<<1|1);
}
for(int i = 0; i < p; i++){
int x,y;
scanf("%d%d",&x,&y);
add(x<<1|1,y<<1);
add(y<<1|1,x<<1);
}
printf("%s\n",check()?"yes":"no");
}
return 0;
}