hdu 4115 Eliminate the Conflict

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

2-sat判定

题意:a和b玩剪刀石头布,玩n轮,b的出拳已经全部给出来,1,2,3分别是石头,布,剪刀。下面给出m行表示a出拳的一下限制,每行的格式为ith jth k,k为0表示ith轮和jth轮a要出一样的拳,k为1表示要出不一样的。问能不能给a安排一套出拳的方法,使得a在n轮里都不会输,不会输包括了平局或者赢。可以保证不输,输出yes,否则no

参考题解:http://www.cnblogs.com/ambition/archive/2011/11/09/Eliminate_the_Conflict.html

  1. a每一轮可以出3种拳,每种拳对应2种状态,即出或不出。所以一轮里面拆出了6个点。
  2. 单纯考虑a自己的出拳情况,可以知道一个简单的事实,a每一轮只可能出一种拳。所以每一轮了,出了石头不能出布和剪刀,出了布不能出石头和剪刀,出了剪刀不能出石头和布。这一点和b无关,也和a本身的那些限制关系无关,所以一开始就可以加上这些必然关系,即加上这些边
  3. 目的是保证了a不输,所以要考虑b每一轮的出拳。
    如果b出了石头,a只能出石头和布,必然关系就是,a不出石头就出布,不出布就出石头
    如果b出了布,a只能出布和剪刀,必然关系是,a不出布必出剪刀,不出剪刀必出布
    如果b出了剪刀,a只能出剪刀和石头,必然关系是,a不出剪刀必出石头,不出石头必出剪刀
  4. 考虑a自身的那些限制条件
    1. ith和jth轮要出相同的拳:ith出了石头jth必出石头,反过来一样。ith出了布jth必出布,反过来一样。ith出了剪刀jth必出剪刀,反过来一样
    2. ith和jth不能出一样的拳:ith出了石头jth必不出石头,反过来一样………………….

这样,所有的限制关系够建好了,就求一次scc,可以判定了

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

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

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

inline void func(int r){ //根据b在第r轮出了什么,可以确定a只能出什么
if(bob[r] == 1){ //b出石头,a只能出石头和布,即不出石头必出布,不出布必出石头
add(r*6+1 , r*6+2); //不出石头必出布
add(r*6+3 , r*6+0); //不出布必出石头
}
else if(bob[r] == 2){ //b出布a必出布和剪刀,不出布必出剪刀,不出剪刀必出布
add(r*6+3 , r*6+4); //不出布必出剪刀
add(r*6+5 , r*6+2); //不出剪刀必出布
}
else{ //b出剪刀,a只能出剪刀和石头,即不出剪刀必出石头,不出石头必出剪刀
add(r*6+5 , r*6+0); //不出剪刀必出石头
add(r*6+1 , r*6+4); //不出石头必出剪刀
}
}

inline void __func(){ //对于每一轮,出了一种拳另外两种都不能出,即每一轮出拳唯一
for(int i = 0; i < n; i++){
add(i*6+0 , i*6+3); //出了石头必不能出布
add(i*6+0 , i*6+5); //出了石头必不能出剪刀
add(i*6+2 , i*6+1); //出了布必不能出石头
add(i*6+2 , i*6+5); //出了布必不能出剪刀
add(i*6+4 , i*6+1); //出了剪刀必不能出石头
add(i*6+4 , i*6+3); //出了剪刀必不能出布
}
}

void build(){
scanf("%d%d",&n,&m);
for(int i = 0; i < 6*n; i++)
e[i].clear();
__func(); //对于每一轮,出了一种拳另外两种都不能出,即每一轮出拳唯一
for(int i = 0; i < n; i++)
scanf("%d",&bob[i]);
for(int i = 0; i < m; i++){
int ith,jth,r,k;
scanf("%d%d%d",&ith,&jth,&k);
func(--ith); //根据b的出拳来决定a的出拳
func(--jth); //根据b的出拳来决定a的出拳
if(k == 0){ //ith和jth要出相同的
add(ith*6+0 , jth*6+0); //ith出了石头jth必出石头
add(jth*6+0 , ith*6+0); //反过来一样
add(ith*6+2 , jth*6+2); //ith出了布jth必出布
add(jth*6+2 , ith*6+2); //反过来一样
add(ith*6+4 , jth*6+4); //ith出了布jth必出布
add(jth*6+4 , ith*6+4); //反过来一样
}
else{ //ith和jth一定不同
add(ith*6+0 , jth*6+1); //ith选石头jth必不选石头
add(jth*6+0 , ith*6+1); //反过来一样
add(ith*6+2 , jth*6+3); //ith选布jth必不选布
add(jth*6+2 , ith*6+3); //反过来一样
add(ith*6+4 , jth*6+5); //ith选剪刀jth必不选剪刀
add(jth*6+4 , ith*6+5); //反过来一样
}
}
}

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;
}
}
}


void scc(){
dcnt = bcnt = top = 0;
cl(dfn,0);
cl(ins,false);
for(int i = 0; i < 6*n; i++)
if(!dfn[i])
tarjan(i);
}

bool check(){
for(int i = 0; i < n; i++)
for(int j = 0; j < 3; j++)
if(belong[i*6+j*2] == belong[i*6+j*2+1])
return false;
return true;
}

int main(){
int cas;
scanf("%d",&cas);
for(int c = 1; c <= cas; c++){
build();
scc();
printf("Case #%d: %s\n",c,check()?"yes":"no");
}
return 0;
}