2023NOIP A层联测25-滈葕

2023-11-07 03:12

文章标签 25 联测 2023noip

本文主要是介绍2023NOIP A层联测25-滈葕，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个 01 权有向图，给每个点赋予 ABCD 中的一个字母使得每条有向边 $(u, v, w)$ 都满足 $w=1\Longleftrightarrow(a_u,a_v)\in\{(A,B),(A,D),(B,A),(B,D),(C,A),(C,B),(C,D)\}$

放一段题解的话

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

可以发现，ABCD 的属性分别表示 A,B,AB,O 型血，一条边表示一次配血试验，边权为 $1$ 代表有凝集反应。

设 $a_i,b_i$ 分别表示第 $i$ 个人是否有凝集原 A,B，则对于出点 $x$ 和入点 $y$ ，凝结原 A 和抗 A 凝集素相遇的条件是 $a_x\land\neg a_y$ ，凝结原 B 和抗 B 凝集素相遇的条件是 $b_x\land\neg b _y$ ，即凝集反应的条件是 $(a_x\land\neg a_y)\lor(b_x\land\neg b _y)$ 。

对于 $w = 1$ ，要满足 $(a_x\land\neg a_y)\lor(b_x\land\neg b _y)=(a_x\lor b_x)\land(a_x\lor\neg b_y)\land(\neg a_y\lor b_x)\land(\neg a_y\lor \neg b_y)$

对于 $w = 0$ ，要满足 $\neg((a_x\land\neg a_y)\lor(b_x\land\neg b _y))=(\neg a_x\lor a_y)\land(\neg b_x\lor b_y)$

发现这两种情况的式子都是 2-sat 的形式，直接做就行了。时间复杂度 $O (n + m)$ 。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1,M=8e6+1;
int n,m,dfn[N<<2],low[N<<2],instack[N<<2],num,cnt1;
int head[N<<2],nxt[M],to[M],cnt,belong[N<<2];
vector<int> s,t[N<<2];
void add(int u,int v)
{to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void dfs(int u)
{dfn[u]=low[u]=++num;s.push_back(u);instack[u]=1;for(int i=head[u];i;i=nxt[i]){if(!dfn[to[i]]){dfs(to[i]);low[u]=min(low[u],low[to[i]]);}else if(instack[to[i]]) low[u]=min(low[u],dfn[to[i]]);}if(dfn[u]==low[u]){++cnt1;int now=0;while(now!=u){now=s.back();t[cnt1].push_back(now);instack[now]=0;belong[now]=cnt1;s.pop_back();}}
}
void ADD(int a,int b,int c,int d)
{add(a+b*n,c+(1-d)*n);add(c+d*n,a+(1-b)*n);
}
int main()
{freopen("dopetobly.in","r",stdin);freopen("dopetobly.out","w",stdout);cin.tie(0)->sync_with_stdio(0);cin>>n>>m;for(int i=1,x,y,w;i<=m;i++){cin>>x>>y>>w;if(w){ADD(x,1,x+2*n,1);ADD(x,1,y+2*n,0);ADD(y,0,x+2*n,1);ADD(y,0,y+2*n,0);}else{ADD(x,0,y,1);ADD(x+2*n,0,y+2*n,1);}}for(int i=1;i<=4*n;i++) if(!dfn[i]) dfs(i);for(int i=1;i<=n;i++){if(belong[i]==belong[i+n]||belong[i+2*n]==belong[i+2*n+n]){cout<<"NO";return 0;}}cout<<"YES"<<"\n";for(int i=1;i<=n;i++){int fl1=(belong[i]<belong[i+n]);int fl2=(belong[i+2*n]<belong[i+2*n+n]);if(fl1&&!fl2) cout<<'A';else if(!fl1&&fl2) cout<<'B';else if(fl1&&fl2) cout<<'C';else cout<<'D';}
}