本文主要是介绍NOIP2023模拟12联测33 滈葕,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目大意
给定一个有 n n n个点 m m m条边的 0 / 1 0/1 0/1权有向图,你要给每个点赋予 A B C D ABCD ABCD中的一个字母使得每条有向边 ( u , v , w ) (u,v,w) (u,v,w)都满足
w = 1 ⇐ ⇒ ( a u , a v ) ∈ { ( A , D ) , ( A , B ) , ( B , D ) , ( B , A ) , ( C , D ) , ( C , A ) , ( C , B ) } w=1\Leftarrow\!\Rightarrow (a_u,a_v)\in\{(A,D),(A,B),(B,D),(B,A),(C,D),(C,A),(C,B)\} w=1⇐⇒(au,av)∈{(A,D),(A,B),(B,D),(B,A),(C,D),(C,A),(C,B)}
如果无解,输出 N O NO NO;否则在第一行输出长度为 n n n的由 A B C D ABCD ABCD构成的字符串,第 i i i个字符表示第 i i i个点的权值。如果有多解,你只需要任意输出一个。
n ≤ 1 0 5 , m ≤ 5 × 1 0 5 , 1 ≤ x , y ≤ n , z ∈ { 0 , 1 } n\leq 10^5,m\leq 5\times 10^5,1\leq x,y\leq n,z\in\{0,1\} n≤105,m≤5×105,1≤x,y≤n,z∈{0,1}, ( x , y , w ) (x,y,w) (x,y,w)中的 x , y x,y x,y可能相同。
题解
先放一段与题目有关的材料。
A B O ABO ABO血型系统是血型系统的一种,把血液分为 A , B , A B , O A,B,AB,O A,B,AB,O四种血型。血液由红细胞和血清等组成,红细胞表面有凝集原,血清内有凝集素。根据红细胞表面有无凝集原 A A A和 B B B来划分血液类型。红细胞上只有凝集原 A A A的为 A A A型血,其血清中有抗 B B B凝集素;红细胞上只有凝集原 B B B的为 B B B型血,其血清中有抗 A A A凝集素;红细胞上两种凝集原都有的为 A B AB AB型血,其血清中无凝集素;红细胞上两种凝集原皆无者为 O O O型,其血清中两种凝集素皆有。有凝集原 A A A的红细胞可被抗凝集素凝集;有凝集原 B B B的红细胞可被抗 B B B凝集素凝集。配血试验是两个人分别提供红细胞和血清并将其混合,观察是否有凝集反应。
可以发现, A B C D ABCD ABCD的属性分别对应 A , B , A B , O A,B,AB,O A,B,AB,O型血,一条边表示一次配血试验。
设 a i , b i a_i,b_i ai,bi分别表示第 i i i个人的红细胞有无凝集原 A , B A,B A,B,则凝集原 A A A和抗 A A A凝集素的相遇条件为 a x ∧ ¬ a y a_x\land \lnot a_y ax∧¬ay,凝集原 B B B和抗 B B B凝集素的相遇条件为 b x ∧ ¬ b y b_x\land \lnot b_y bx∧¬by。因此,每个条件为 z = ( a x ∧ ¬ a y ) ∨ ( b x ∧ ¬ b y ) z=(a_x\land \lnot a_y)\lor (b_x\land \lnot b_y) z=(ax∧¬ay)∨(bx∧¬by),那么
- 如果 z = 0 z=0 z=0,则满足 ¬ ( a x ∧ ¬ a y ) ∧ ¬ ( b x ∧ ¬ b y ) \lnot(a_x\land \lnot a_y)\land \lnot(b_x\land \lnot b_y) ¬(ax∧¬ay)∧¬(bx∧¬by),即 ( ¬ a x ∨ a y ) ∧ ( ¬ b x ∨ b y ) (\lnot a_x \lor a_y)\land(\lnot b_x\lor b_y) (¬ax∨ay)∧(¬bx∨by)
- 如果 z = 1 z=1 z=1,则满足 ( a x ∧ ¬ a y ) ∨ ( b x ∧ ¬ b y ) (a_x\land \lnot a_y)\lor (b_x\land \lnot b_y) (ax∧¬ay)∨(bx∧¬by),即 ( a x ∨ b x ) ∧ ( a x ∨ ¬ b y ) ∧ ( b x ∨ ¬ a y ) ∧ ( ¬ a y ∨ ¬ 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) (ax∨bx)∧(ax∨¬by)∧(bx∨¬ay)∧(¬ay∨¬by)
这两种情况都是 2 − S A T 2-SAT 2−SAT的形式,对于每个 i i i,在 2 − S A T 2-SAT 2−SAT的图上令 i i i表示 a i a_i ai, i + n i+n i+n表示 ¬ a i \lnot a_i ¬ai, i + 2 n i+2n i+2n表示 b i b_i bi, i + 3 n i+3n i+3n表示 ¬ b i \lnot b_i ¬bi,然后用 t a r j a n tarjan tarjan即可。
时间复杂度为 O ( n + m ) O(n+m) 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;
}
这篇关于NOIP2023模拟12联测33 滈葕的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!