TIOJ 1149 4.滿漢全席 [2-SAT]

3    75828    poao899    -8K    75MS    G++     1.01K     2010-04-22 17:40:51                                  .


轉一轉就變2-SAT了


這是2-SAT經典文：按我



其實我覺得最麻煩是建圖很容易建歪˙˙



//************************************

#include<stdio.h>
bool con[40][40], pos, v[40];
char buf[100], c, d;
int n, m, K, a, b, $;
/*
m 0~n-1  h n~2n-1
*/
bool dfs(int now){
	v[now]= 1;
	if(now-$==n|| $-now==n)return 0;
	for(int i=0; i<2*n; i++)
		if(con[now][i]&& !v[i]&& !dfs(i))
			return 0;
	return 1;
}
int main(){
	gets(buf);
	sscanf(buf, "%d", &K);
	while(K--){
		pos= 1;
		gets(buf);
		sscanf(buf, "%d%d", &n, &m);
		for(int i=0; i<n*2; i++)
			for(int j=0; j<n*2; j++)
				con[i][j]= 0;
		for(int i=0; i<m; i++){
			gets(buf);
			sscanf(buf, "%c%d %c%d", &c, &a, &d, &b);
			con[a+(c=='h'?n:0)-1][b+(d=='m'?n:0)-1]= 1;
			con[b+(d=='h'?n:0)-1][a+(c=='m'?n:0)-1]= 1;
		}
		for($=0; pos&&$<n; $++){
			for(int j=0; j<2*n; j++)v[j]= 0;
			pos= dfs($);
			if(!pos){
				for(int j=0; j<2*n; j++)v[j]= 0;
				$+=n; pos= dfs($); $-=n;
			}
		}
		puts(pos? "GOOD": "BAD");
	}
}