题目链接
题目大意
有n场比赛,每场比赛可以选择A,B,C类型中的一个。
大多数比赛自身有所限制,即不能选择某一个类型(A/B/C)。只有少数(共\(d\)个)没有限制。
除此之外还有\(m\)个限制\((i,h_i,j,h_j)\),表示若第\(i\)场比赛选了\(h_i\),则第\(j\)场比赛必须选\(h_j\)。
解题思路
依赖性的限制,多半是2-sat。
但是有些比赛有3种选择。而3-sat是NP问题。
可以发现\(d\)非常小,所以可以强制要求有3种选择的比赛也有限制。
然后照常建边,跑2-sat即可。
不过尤其坑人的是要输出方案,具体可以见2-sat模板。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 200010
#define M 300010
using namespace std;
int nxt[M<<1],to[M<<1],head[N],cnt;
void add(int u,int v)
{
nxt[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
}
int dfn[N],id[N],low[N],idn,uid;
int sta[N],top;
bool in[N];
void tarjan(int u)
{
dfn[u]=low[u]=++idn;
sta[top++]=u;
in[u]=true;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[v],low[u]);
}
else if(in[v])low[u]=min(dfn[v],low[u]);
}
if(dfn[u]==low[u])
{
int v;
++uid;
do{
v=sta[--top];
in[v]=false;
id[v]=uid;
}
while(u!=v);
}
}
int ban[N],n,m;
inline int get_id(int u,int d){return u*3+d;}
bool solve(void)
{
for(int i=1;i<=(n+1)*3;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++)
if(id[get_id(i,(ban[i]+1)%3)]==id[get_id(i,(ban[i]+2)%3)]) return false;
return true;
}
struct Q{
int l,x,r,y;
}q[M];
int get_nxt(int u,int p){p=(p+1)%3;return ban[u]==p?(p+1)%3:p;}
void work(void)
{
memset(head,0,sizeof(head));
cnt=0;
memset(id,0,sizeof(id));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
uid=top=idn=0;
for(int i=1;i<=m;i++)
{
if(ban[q[i].l]==q[i].x) continue;
if(ban[q[i].r]==q[i].y){add(get_id(q[i].l,q[i].x),get_id(q[i].l,get_nxt(q[i].l,q[i].x)));continue;}
add(get_id(q[i].l,q[i].x),get_id(q[i].r,q[i].y));
add(get_id(q[i].r,get_nxt(q[i].r,q[i].y)),get_id(q[i].l,get_nxt(q[i].l,q[i].x)));
}
if(!solve()) return;
for(int i=1;i<=n;i++)
{
int p1=(ban[i]+1)%3;
int p2=(ban[i]+2)%3;
if(id[get_id(i,p1)]>id[get_id(i,p2)]) p1=p2;
putchar('A'+p1);
}
exit(0);
}
void dfs(int u)
{
while(u<=n && ban[u]!=-1) u++;
if(u>n){work();return;}
ban[u]=0;
dfs(u+1);
ban[u]=1;
dfs(u+1);
ban[u]=-1;
}
char str[N];
char a1[3],a2[3];
int main()
{
int d;
scanf("%d%d",&n,&d);
scanf("%s",str+1);
for(int i=1;i<=n;i++)
if(str[i]=='x') ban[i]=-1;
else ban[i]=str[i]-'a';
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%s%d%s",&u,a1,&v,a2);
q[i]=(Q){u,a1[0]-'A',v,a2[0]-'A'};
}
dfs(1);
printf("-1");
return 0;
}