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