BZOJ2199 [Usaco2011 Jan]奶牛议会
? 解题记录 ? ? BZOJ ? ? 2-SAT ?    2017-07-28 21:23:01    484    0    0

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

 3 4
 1 Y 2 N
 1 N 2 N
 1 Y 3 Y
 1 Y 2 Y​



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

 

上一篇: 洛谷P1525 关押罪犯

下一篇: 洛谷 P2341 [HAOI2006]受欢迎的牛

484 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航