2023NOIP A层联测25 T4 滈葕
配血实验与2-SAT。
思路
\(z=1\) 表示配血实验发生凝集反应,设 \(a_i,b_i\) 分别表示第 \(i\) 个人有无凝集原 A,B。(无凝集原 A,肯定有抗 A 凝集素,B同理)那么发生反应的必要条件是 \(a_x \and \neg a_y\) 或 \(b_x \and \neg b_y\),所以 \(z=(a_x\and \neg a_y) \or (b_x \and \neg b_y)\)。
若 \(z=0\) 则有 \(\neg(a_x\and \neg a_y) \and \neg (b_x \and \neg b_y)=(\neg a_x \or a_y) \and (\neg b_x \and b_y)\)。
若 \(z=1\) 则有 \(z=(a_x\and \neg a_y) \or (b_x \and \neg b_y)=(a_x \or b_x)\and(a_x \or \neg b_y)\and (\neg a_y \or b_x)\and (\neg a_y \or \neg b_y)\)。
这两个都可以使用 2-SAT 解决。
CODE
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
struct node
{
int to,nxt;
}edge[maxn*8];
int n,m,tot,dfntot,num;
int dfn[maxn],low[maxn],id[maxn],A[maxn][2],B[maxn][2],head[maxn];
bool vis[maxn];
stack<int>stk;
void add(int x,int y)
{
tot++;
edge[tot].to=y;
edge[tot].nxt=head[x];
head[x]=tot;
}
void dfs(int u)
{
stk.push(u),dfn[u]=low[u]=++dfntot,vis[u]=1;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(!dfn[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
num++;
while(stk.top()!=u) vis[stk.top()]=0,id[stk.top()]=num,stk.pop();
vis[stk.top()]=0,id[stk.top()]=num;
stk.pop();
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) A[i][0]=i,A[i][1]=i+n,B[i][0]=i+2*n,B[i][1]=i+3*n;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(z==0)
{
add(A[x][1],A[y][1]),add(A[y][0],A[x][0]);//!a a
add(B[x][1],B[y][1]),add(B[y][0],B[x][0]);//!b b
}
else
{
add(A[x][0],B[x][1]),add(B[x][0],A[x][1]);
add(A[x][0],B[y][0]),add(B[y][1],A[x][1]);
add(A[y][1],B[x][1]),add(B[x][0],A[y][0]);
add(A[y][1],B[y][0]),add(B[y][1],A[y][0]);
}
}
for(int i=1;i<=n*4;i++) if(!dfn[i]) dfs(i);
for(int i=1;i<=n;i++) if(id[A[i][0]]==id[A[i][1]]||id[B[i][0]]==id[B[i][1]]) printf("NO"),exit(0);
printf("YES\n");
for(int i=1;i<=n;i++)
{
if(id[A[i][0]]<id[A[i][1]]&&id[B[i][0]]<id[B[i][1]]) printf("D");
if(id[A[i][0]]<id[A[i][1]]&&id[B[i][0]]>id[B[i][1]]) printf("A");
if(id[A[i][0]]>id[A[i][1]]&&id[B[i][0]]<id[B[i][1]]) printf("B");
if(id[A[i][0]]>id[A[i][1]]&&id[B[i][0]]>id[B[i][1]]) printf("C");
}
}