题解：P10969 Katu Puzzle

题意

有

n

个点和

m

条边，给每个点赋值为

0

或

1

，使得每条边满足

x_i \ \text{op} \ y_i = c_i

。

分析

满足 2-sat 模型，这里不做赘述。

考虑建边，对原有边分类讨论：

$AND = 1 : x=1,\ y=1$
$AND = 0 : x=1 \Rightarrow y=0 ,\ y=1 \Rightarrow x=0$
$OR = 1 : x=0 \Rightarrow y=1 ,\ y=0 \Rightarrow x=1$
$OR = 0 : x=0,\ y=0$
$XOR = 0 : x=0 \Leftrightarrow y=1 ,\ x=1 \Leftrightarrow y=0$
$XOR =1 : x=1 \Leftrightarrow y=1 ,\ x=0 \Leftrightarrow y=0$

可以发现对于 2,3,5,6，都是通过一个变量来推导出另一个变量，而对于 1,4，是直接确定了两个变量的值，是本题的一个难点。

考虑 1，发现当

x=0

或

y=0

时一定不能成立，于是新建一个节点

T

，让

x=0

和

y=0

连向

T

，再让

T

连向所有点。这样，如果推出

x=0

或

y=0

，就一定能推出

T

，而

T

又能推出所有节点，于是成环。4 同理。

考虑判定有无一组解，先判定

x=0 \Rightarrow x=1

是否成立，如果成立则无解；再判定

x=0 \nRightarrow T

和

x=1 \nRightarrow T

是否至少有一个成立，如果没有则无解（因为如果有一个成立，

x

就可以取该值而避免冲突）。

code

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=205;
char rdc()
{
	char c=getchar();
	while(c<'A' or c>'Z')c=getchar();
	return c;
}
int rd()
{
	char c=getchar();
	int res=0;
	while(!isdigit(c))c=getchar();
	while(isdigit(c))res=res*10+c-'0',c=getchar();
	return res;
}
vector<int>g[N];
int n,m,T;
int scc[N],num;
int stk[N],tp;
bool instk[N];
int low[N],dfn[N],inx;
void tar(int x) // tarjan 模板
{
	if(dfn[x])return;
	stk[++tp]=x;
	instk[x]=1;
	low[x]=dfn[x]=++inx;
	for(auto y:g[x])
	{
		if(!dfn[y])
		{
			tar(y);
			low[x]=min(low[x],low[y]);
		}
		else if(instk[y])low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x])
	{
		int p;
		num++;
		do{
			p=stk[tp--];
			instk[p]=0;
			scc[p]=num;
		}while(p!=x);
	}
}

signed main()
{
	n=rd();m=rd();
	T=n*2+1;
	for(int i=1;i<=n*2;i++)g[T].push_back(i); // T 通向所有点
	while(m--)
	{
		int x=rd()+1,y=rd()+1,c=rd();
		char op=rdc();
		if(op=='A') // 分类建边
		{
			if(c==1){
				g[x].push_back(T);
				g[y].push_back(T);
			}
			else {
				g[x+n].push_back(y);
				g[y+n].push_back(x);
			}
		}
		else if(op=='O')
		{
			if(c==1){
				g[x].push_back(y+n);
				g[y].push_back(x+n);
			}
			else {
				g[x+n].push_back(T);
				g[y+n].push_back(T);
			}
		}
		else {
			if(c==1){
				g[x].push_back(y+n);
				g[x+n].push_back(y);
				g[y].push_back(x+n);
				g[y+n].push_back(x);
			}
			else {
				g[x].push_back(y);
				g[y].push_back(x);
				g[x+n].push_back(y+n);
				g[y+n].push_back(x+n);
			}
		}
	}
	for(int i=1;i<=n*2+1;i++)tar(i);
	bool fl=1;
	for(int i=1;i<=n;i++)
	{
		if(scc[i]==scc[i+n] or (scc[i]==scc[T] and scc[i+n]==scc[T])) // 判定有无解，见分析 
		{
			fl=0;
			break;
		}
	}
	if(fl)puts("YES");
	else puts("NO");
}

题解：P10969 Katu Puzzle

文章操作

题意

分析

code

相关推荐

评论

题解：P10969 Katu Puzzle