hdu4115

 source: http://acm.hdu.edu.cn/showproblem.php?pid=4115

  title:    Eliminate the Conflict

 

/*
题解转自： http://www.haogongju.net/art/759654
题解: 
题目意思很简单，两个人石头剪刀布，一个人的出法是确定的，另一个人的出法有一定约束，某两次要相同或者不同，问你第二个人能否全部都不失败。题目还是很容易想到2-sat的，不过按照官方题解里说的每次出拳拆分成两个相对点的建图方法相当麻烦，小明哥按照那种方法建图就写了5k那么长，比较容易理解的方法是拆六个点：
石头(R)， 非石头(~R)
   布(P)， 非布(~P)
剪刀(S)， 非剪刀(~S)
每次只能三者取一个，那么就是如果出了一个，另外两个就不能出
R->~P, R->~S, P->~R, P->~S, S->~R, S->~P
然后根据对方的出法，就只能出平局和胜局两种出法
比如：如果对方是石头(R)，那么只能出R和P，非R即P，非P即R
~R->P, ~P->R
最后就是加入约束关系，如果两次必须相同:
R1<->R2, P1<->P2, S1<->S2 均是双向边
如果不同也是一样
R1->~R2, R2->~R1, ......
这样建好图之后跑一边2-sat模板就能A掉了
*/
#include <stdio.h>
const int N=10005;
const int M=10005;
const int V=N*6;
const int E=8*N+6*M;

struct e{
	int v;
	e* nxt;
}es[E];
e* fir[V];
int id[V], pre[V], low[V], s[V], stop, cnt, scnt;
int en;

void tarjan(int v, int n){
	int t, minc = low[v] = pre[v] = cnt++;
	e* cur;
	s[stop++] = v;
	for(cur = fir[v]; cur ; cur = cur->nxt){
		if(-1 == pre[cur->v]) tarjan(cur->v, n);
		if(low[cur->v] < minc) minc = low[cur->v];
	}
	if(minc < low[v]){
		low[v] = minc;
		return;
	}
	do{
		id[t = s[--stop]] = scnt; low[t] = n;
	}while(t != v);
	++scnt;   //强连通分量的个数
}
inline void add_e(int u, int v){
	es[en].v = v; es[en].nxt = fir[u]; fir[u] = &es[en++];
}
void getSCC(int n){  //get strongly connected component
	stop = cnt = scnt = 0;
	int i;
	for(i = 0; i < n; i++) pre[i] = -1;
	for(i = 0; i < n; i++) if(-1 == pre[i]) tarjan(i, n);
}
int n;
int bs[N];
//i表示第i仑，t为0,1,2分表表示rock，paper，u为0表示"是"，为1表示"不是"
int getid(int i, int t, int u){
	return i*6+t*2+u;
}
bool input(){
	int m, i, a, b, k;
	scanf("%d%d", &n, &m);
	for(i=0; i<n*6; i++){
		fir[i]=NULL;
	}
	en=0;
	for(i=0; i<n; i++){
		add_e(getid(i, 0, 0), getid(i, 1, 1));
		add_e(getid(i, 0, 0), getid(i, 2, 1));
		add_e(getid(i, 1, 0), getid(i, 0, 1));
		add_e(getid(i, 1, 0), getid(i, 2, 1));
		add_e(getid(i, 2, 0), getid(i, 0, 1));
		add_e(getid(i, 2, 0), getid(i, 1, 1));
	}
	for(i=0; i<n; i++){
		scanf("%d", bs+i);
		bs[i]--;
		if(bs[i]==0){
			add_e(getid(i, 1, 1), getid(i, 0, 0));
			add_e(getid(i, 0, 1), getid(i, 1, 0));
		}else if(bs[i]==1){
			add_e(getid(i, 1, 1), getid(i, 2, 0));
			add_e(getid(i, 2, 1), getid(i, 1, 0));
		}else{
			add_e(getid(i, 2, 1), getid(i, 0, 0));
			add_e(getid(i, 0, 1), getid(i, 2, 0));
		}
	}
	for(i=0; i<m; i++){
		scanf("%d%d%d", &a, &b, &k);
		a--;
		b--;
		if(k==0){
			add_e(getid(a, 0, 0), getid(b, 0, 0));
			add_e(getid(a, 1, 0), getid(b, 1, 0));
			add_e(getid(a, 2, 0), getid(b, 2, 0));
			add_e(getid(b, 0, 0), getid(a, 0, 0));
			add_e(getid(b, 1, 0), getid(a, 1, 0));
			add_e(getid(b, 2, 0), getid(a, 2, 0));
		}else{
			add_e(getid(a, 0, 0), getid(b, 0, 1));
			add_e(getid(a, 1, 0), getid(b, 1, 1));
			add_e(getid(a, 2, 0), getid(b, 2, 1));
			add_e(getid(b, 0, 0), getid(a, 0, 1));
			add_e(getid(b, 1, 0), getid(a, 1, 1));
			add_e(getid(b, 2, 0), getid(a, 2, 1));
		}
	}
	return true;
}

int ca=0;
void solve(){
	getSCC(6*n);
	int i;
	for(i=0; i<6*n; i+=2){
		if(id[i]==id[i+1]) break;
	}
	if(i>=6*n){
		printf("Case #%d: yes\n", ++ca);
	}else{
		printf("Case #%d: no\n", ++ca);
	}
}
int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		input();
		solve();
	}
	return 0;
}