2023NOIP A层联测25-滈葕

link

放一段题解的话

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\wedge \neg a_y$，凝结原 B 和抗 B 凝集素相遇的条件是 $b_x\wedge \neg b_y$，即凝集反应的条件是 $(a_x\wedge \neg a_y)\vee (b_x\wedge \neg b_y)$。

对于 $w=1$，要满足 $(a_x\wedge \neg a_y)\vee (b_x\wedge \neg b_y)=(a_x\vee b_x)\wedge (a_x\vee \neg b_y)\wedge (\neg a_y\vee b_x)\wedge (\neg a_y\vee \neg b_y)$

对于 $w=0$，要满足 $\neg ((a_x\wedge \neg a_y)\vee (b_x\wedge \neg b_y))=(\neg a_x\vee a_y)\wedge (\neg b_x\vee b_y)$

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

代码如下：

#include
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';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77