【BZOJ 2199】[Usaco2011 Jan] 奶牛议会

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2199
离线版题目：http://paste.ubuntu.com/22149982/

仍然是2-sat
一开始觉得这货，拓扑关系上的父亲对该决策有影响
遂wa
后来想一想，貌似父亲那过来的条件只是充分的，不是必要的
于是O(n^2)暴力验证，ac

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 8000+9;

int T,nxt[MAXN],to[MAXN],head[MAXN],mark[MAXN];
int que[MAXN],cnt,vout[MAXN],n,m;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9'){c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret;
}

inline void AddEdge(int u, int v){
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline bool DFS(int w){
	if (mark[w^1]) return false;
	else if (mark[w]) return true;
	mark[w] = 1; que[++cnt] = w;
	
	for (int i=head[w];i;i=nxt[i]) 
		if (!DFS(to[i])) return false;
	return true;
}

inline bool Get_Ans(){
	for (int i=2;i<=n*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
		cnt = 0; if (DFS(i)) vout[i/2] = 1;
		for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
		cnt = 0; if (DFS(i+1)) vout[i/2] += 2;
		for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
		if (!vout[i/2]) return false;
	}
	return true;
}

int main(){
	n = read(); m = read();
	for (int i=1,a,b,ra,rb;i<=m;i++) { char tmp; 
		a = ra = read()*2; scanf("%c",&tmp);
		if (tmp == 'Y') ra++; else a++;
		b = rb = read()*2; scanf("%c",&tmp);
		if (tmp == 'Y') rb++; else b++;
		AddEdge(ra,b); AddEdge(rb,a);
	} 
	if (!Get_Ans()) printf("IMPOSSIBLE");
	else for (int i=1;i<=n;i++) {
		if (vout[i] == 3) printf("?");
		else if (vout[i] == 1) printf("Y");
		else printf("N");
	}
	return 0;
}