Tag:2-SAT/建图,思维
思路:
$$ \large a \land b \land c <=> \large \lnot a \rightarrow b \quad \large \lnot a \rightarrow c \quad \large \lnot b \rightarrow a \quad \large \lnot b \rightarrow c \quad \large \lnot c \rightarrow a \quad \large \lnot c \rightarrow b $$
原题每一个询问,可以等价于上式,具体含义就是:
因为对于关系而言,越少的关系,我们设置的限制就越少,因此实际上,对于每个询问,我们只需要保证两个点的查询是真的即可,反过来就是说,我们可以通过一个推出另外两个是真的。
这样我们就建出了$SAT$图,之后套板子判断即可。
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=10010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=5010;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
struct node{
int id,col;
};
int dfn[N*2],low[N*2],timestamp,id[N*2],scc_cnt;
int e[M*6],ne[M*6],idx,h[N*2];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool in_stk[N*2];
stack<int>stk;
void tarjan(int u)
{
dfn[u]=low[u]=++timestamp;
stk.push(u);in_stk[u]=true;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!dfn[j])
{
tarjan(j);
low[u]=min(low[u],low[j]);
}else if(in_stk[j])low[u]=min(low[u],dfn[j]);
}
if(low[u]==dfn[u])
{
int y;scc_cnt++;
do
{
y=stk.top();stk.pop();
in_stk[y]=false;
id[y]=scc_cnt;//注意不要写错
}while(y!=u);
}
}
void solve()
{
int n,k;
cin>>k>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
node a,b,c;
char op;
cin>>a.id>>op;
a.col=(op=='R');
cin>>b.id>>op;
b.col=(op=='R');
cin>>c.id>>op;
c.col=(op=='R');
add(a.id+(a.col^1)*k,b.id+b.col*k);
add(a.id+(a.col^1)*k,c.id+c.col*k);
add(b.id+(b.col^1)*k,a.id+a.col*k);
add(b.id+(b.col^1)*k,c.id+c.col*k);
add(c.id+(c.col^1)*k,a.id+a.col*k);
add(c.id+(c.col^1)*k,b.id+b.col*k);
}
for(int i=1;i<=2*k;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=k;i++)
if(id[i]==id[i+k])
{
cout<<"-1"<<endl;
return ;
}
vector<char>ans(k+1);
for(int i=1;i<=k;i++)
if(id[i]>id[i+k])ans[i]='R';
else ans[i]='B';
for(int i=1;i<=k;i++)cout<<ans[i];
cout<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
#endif
solve();
return 0;
}