Description

由于对Farmer John的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统： M只到场的奶牛 (1 <= M <= 4000) 会给N个议案投票(1 <= N <= 1,000) 。每只奶牛会对恰好两个议案 B_i and C_i (1 <= B_i <= N; 1 <= C_i <= N)投出“是”或“否”（输入文件中的'Y'和'N'）。他们的投票结果分别为VB_i (VB_i in {'Y', 'N'}) and VC_i (VC_i in {'Y', 'N'})。最后，议案会以如下的方式决定：每只奶牛投出的两票中至少有一票和最终结果相符合。例如Bessie给议案1投了赞成'Y'，给议案2投了反对'N'，那么在任何合法的议案通过方案中，必须满足议案1必须是'Y'或者议案2必须是'N'（或者同时满足）。给出每只奶牛的投票，你的工作是确定哪些议案可以通过，哪些不能。如果不存在这样一个方案，输出"IMPOSSIBLE"。如果至少有一个解，输出： Y 如果在每个解中，这个议案都必须通过 N 如果在每个解中，这个议案都必须驳回 ? 如果有的解这个议案可以通过，有的解中这个议案会被驳回考虑如下的投票集合： - - - - - 议案 - - - - - 1 2 3 奶牛 1 YES NO 奶牛 2 NO NO 奶牛 3 YES YES 奶牛 4 YES YES 下面是两个可能的解： * 议案 1 通过（满足奶牛1，3，4） * 议案 2 驳回（满足奶牛2） * 议案 3 可以通过也可以驳回（这就是有两个解的原因）事实上，上面的问题也只有两个解。所以，输出的答案如下： YN?

Input

* 第1行：两个空格隔开的整数：N和M * 第2到M+1行：第i+1行描述第i只奶牛的投票方案：B_i, VB_i, C_i, VC_i

Output

* 第1行：一个含有N个字符的串，第i个字符要么是'Y'（第i个议案必须通过），或者是'N' （第i个议案必须驳回），或者是'?'。如果无解，输出"IMPOSSIBLE"。

Sample Input

Sample Output

YN?

HINT

Source

2-SAT裸题。然而还是太弱刷了一会评测机……

这里献上对拍：https://pan.baidu.com/s/1eRHSlJ8，把代码放进2SAT.cpp

不用任何文件输入输出即可

值得注意的是边界问题和拆点问题，详见注释：

/*
	2-SAT究极脑补版 
*/
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 5e3 + 100;
const int maxm = 1e4 + 100;
struct edge {
	int v, next;
}e[maxm];
int cnt, n, m;
int head[maxn], undec[maxn];
bool vis[maxn]; 
void adde(const int &u, const int &v) {
	e[cnt] = (edge) {v, head[u]};
	head[u] = cnt++;
}

/*读入优化*/
int read(){
	int ret = 0;
	char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c >= '0' && c <= '9') 
		ret = ret * 10 + c - '0', c = getchar();
	return ret;
}

#define OPP(x) (x ^ 1)
#define TRUE(x) (x << 1)
#define FALSE(x) ((x << 1) ^ 1)
bool SAT(int u) {
	if(vis[OPP(u)])	return false;
	vis[u] = 1;/*沿途标记*/
	for(int i = head[u]; i != -1; i = e[i].next) {
		int v = e[i].v;
		if(!vis[v]) {
			int ret = SAT(v);
			if(!ret) return false;
		}
	}
	return true;
}

bool getans() {
	for(int i = 1; i <= n; i++) {
		undec[TRUE(i)] = SAT(TRUE(i)); /*每一次2SAT是一次全新的操作*/
		memset(vis, 0, sizeof(vis));   /*vis数组归零是非常有必要的*/
		undec[FALSE(i)] = SAT(FALSE(i));
		memset(vis, 0, sizeof(vis));
	}	
	for(int i = 1; i <= n; i++) { /*手贱1e4年，专业打错循环*/
		if(!undec[TRUE(i)] && !undec[FALSE(i)])
			{printf("IMPOSSIBLE");return 0;}
	}
	for(int i = 1; i <= n; i++) {
		if(undec[TRUE(i)] && undec[FALSE(i)])	printf("?");
		else if(undec[TRUE(i)])	printf("Y");
		else if(undec[FALSE(i)])  printf("N");	
	}
	return true;
}

int main() {
	memset(head, -1, sizeof(head));
	n = read(), m = read();
	for(int i = 1; i <= m; i++) {
		char uc, vc;
		bool uj, vj;
		int u, v;
		u = read(), uc = getchar();
		v = read(), vc = getchar();
		uj = uc == 'Y';
		vj = vc == 'Y';
		/*加边操作可以这样简化*/
		adde(TRUE(v) + vj, TRUE(u) + !uj);
		adde(TRUE(u) + uj, TRUE(v) + !vj);
	}
	getans();
	return 0;
}

Rockdu's Blog