题目链接 https://www.luogu.com.cn/problem/P3703
题目大意
有 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 模板 https://www.luogu.com.cn/problem/P4782 , 大概就是判断其正反点 dfs 序的大小.
代码
- #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;
- }
[NOI2017]游戏
来源: http://www.bubuko.com/infodetail-3383944.html