当前位置：首页 > news >正文

NOIP2023模拟12联测33 滈葕

news 来源：原创 2024/5/9 23:40:01

题目大意

给定一个有 $n$ 个点 $m$ 条边的 $0/1$ 权有向图，你要给每个点赋予 $A BC D$ 中的一个字母使得每条有向边 $(u, v, w)$ 都满足

$w=1\Leftarrow\!\Rightarrow (a_u,a_v)\in\{(A,D),(A,B),(B,D),(B,A),(C,D),(C,A),(C,B)\}$

如果无解，输出 $NO$ ；否则在第一行输出长度为 $n$ 的由 $A BC D$ 构成的字符串，第 $i$ 个字符表示第 $i$ 个点的权值。如果有多解，你只需要任意输出一个。

$n\leq 10^5,m\leq 5\times 10^5,1\leq x,y\leq n,z\in\{0,1\}$ ， $(x, y, w)$ 中的 $x, y$ 可能相同。

题解

先放一段与题目有关的材料。

$A BO$ 血型系统是血型系统的一种，把血液分为 $A, B, A B, O$ 四种血型。血液由红细胞和血清等组成，红细胞表面有凝集原，血清内有凝集素。根据红细胞表面有无凝集原 $A$ 和 $B$ 来划分血液类型。红细胞上只有凝集原 $A$ 的为 $A$ 型血，其血清中有抗 $B$ 凝集素；红细胞上只有凝集原 $B$ 的为 $B$ 型血，其血清中有抗 $A$ 凝集素；红细胞上两种凝集原都有的为 $A B$ 型血，其血清中无凝集素；红细胞上两种凝集原皆无者为 $O$ 型，其血清中两种凝集素皆有。有凝集原 $A$ 的红细胞可被抗凝集素凝集；有凝集原 $B$ 的红细胞可被抗 $B$ 凝集素凝集。配血试验是两个人分别提供红细胞和血清并将其混合，观察是否有凝集反应。

可以发现， $A BC D$ 的属性分别对应 $A, B, A B, O$ 型血，一条边表示一次配血试验。

设 $a_i,b_i$ 分别表示第 $i$ 个人的红细胞有无凝集原 $A, B$ ，则凝集原 $A$ 和抗 $A$ 凝集素的相遇条件为 $a_x\land \lnot a_y$ ，凝集原 $B$ 和抗 $B$ 凝集素的相遇条件为 $b_x\land \lnot b_y$ 。因此，每个条件为 $z=(a_x\land \lnot a_y)\lor (b_x\land \lnot b_y)$ ，那么

如果 $z = 0$ ，则满足 $\lnot(a_x\land \lnot a_y)\land \lnot(b_x\land \lnot b_y)$ ，即 $(\lnot a_x \lor a_y)\land(\lnot b_x\lor b_y)$
如果 $z = 1$ ，则满足 $(a_x\land \lnot a_y)\lor (b_x\land \lnot b_y)$ ，即 $(a_x\lor b_x)\land(a_x\lor \lnot b_y)\land(b_x\lor \lnot a_y)\land(\lnot a_y\lor \lnot b_y)$

这两种情况都是 $2 - S A T$ 的形式，对于每个 $i$ ，在 $2 - S A T$ 的图上令 $i$ 表示 $a_i$ ， $i + n$ 表示 $\lnot a_i$ ， $i + 2 n$ 表示 $b_i$ ， $i + 3 n$ 表示 $\lnot b_i$ ，然后用 $t a r jan$ 即可。

时间复杂度为 $O (n + m)$ 。

code

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int n,m,ct=0,tp=0,cl=0,dfn[N*4+5],low[N*4+5],st[N*4+5],co[N*4+5];
vector<int>g[N*4+5];
void add(int xx,int yy){g[xx].push_back(yy);
}
void tarjan(int u){dfn[u]=low[u]=++ct;st[++tp]=u;for(int v:g[u]){if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(!co[v]) low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){++cl;while(st[tp]!=u) co[st[tp--]]=cl;co[st[tp--]]=cl;}
}
int main()
{
//	freopen("dopetobly.in","r",stdin);
//	freopen("dopetobly.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1,x,y,z;i<=m;i++){scanf("%d%d%d",&x,&y,&z);if(!z){add(x,y);add(y+n,x+n);add(x+2*n,y+2*n);add(y+3*n,x+3*n);}else{add(x+n,x+2*n);add(x+3*n,x);add(x+n,y+3*n);add(y+2*n,x);add(x+3*n,y+n);add(y,x+2*n);add(y,y+3*n);add(y+2*n,y+n);}}for(int i=1;i<=n*4;i++){if(!dfn[i]) tarjan(i);}for(int i=1;i<=n;i++){if(co[i]==co[i+n]||co[i+2*n]==co[i+3*n]){printf("NO");return 0;}}printf("YES\n");for(int i=1;i<=n;i++){int x=co[i]<co[i+n],y=co[i+2*n]<co[i+3*n];if(x&&!y) printf("A");else if(!x&&y) printf("B");else if(x&&y) printf("C");else printf("D");}return 0;
}