P9220 [TAOI-1] - 椎名真昼题解 - JustPureH2O 的博客

Done

您已获得最佳的阅读体验

题目地址：P9220

题目难度：提高+/省选-

Alice 和 Bob 正在玩一款游戏，给定一个有向图，每个点初始有一个颜色（黑或白）。
双方轮流进行操作，Alice 先手，每次操作选定一个节点，将所有从该点开始，能到达的点（包括自身）颜色翻转。如果某次操作后所有节点都变为白色，则进行该次操作的人胜利。
假如双方都采用最优策略使得自己胜利，或者如果自己无法胜利，使得对方无法胜利。
给你节点的初始状态，请你求出最终的胜者，亦或者，没有胜者。
定义点能到达点，当且仅当存在数列，其中，使得，存在有向边，且，。
对于所有测试数据，，，。

首先，如果这个游戏无法在两步及以内结束的话，就可以直接算平局了。因为若是超过两步，认为自己会输的那一方将会想尽办法不让你赢，具体表现就是重复另一方先前的操作，让图变为另一方操作前的状态，最终陷入死循环。因此我们只需关注一步定胜负和两步定胜负的情况。

根据题目中对两点能互相到达的定义，我们很容易知道——若对某个中的点进行一次操作，那么同处于这个的其他点的颜色也都会翻转（但不止这些点的颜色被翻转）。这启发我们处理出原图中的所有强连通分量。此时不难发现，如果某个中存在异色点，那么无论怎么翻转，它们都不会变为统一颜色，于是这种情况可以直接判成平局；否则我们就把这个强连通分量染成内部点的颜色。

处理出所有的强连通分量后，我们再把一个强连通分量整体看作一个新点，建在新图上（即缩点），此时新图必定是一个有向无环图。那么如果在某个强连通分量中的某个点上进行操作，新图中该强连通分量的子节点一定也会受到影响从而变化颜色。至此我们便理清了操作与颜色翻转之间的规律。

现在来讨论必胜局面。因为游戏不会超过两轮，所以如果先手的想要获胜，她就必须在第一轮胜利，否则要么胜、要么平局。也因此，在新建的有向无环图上，有且仅能存在一个节点，使得它的子树包含新图中所有的黑色，且不包含任何白色。这样一来先手才能一次把这些黑色点转化成白色从而获胜。如果这个子树不完全是黑色，或者是存在多个节点满足要求，都不能保证获胜（但也不代表必输，因为还存在平局）。

再来看这边，他如果想要获胜，就只能抓住第二轮这唯一的机会。有三种可能性：

全图均为白色节点。这样只能选择白色节点染黑，此时只需重复她的操作即可恢复全图到全白的状态。
仅有两个孤立的黑色。此时选择其一染白，仅需染白另一个即可。
一个白色和一个黑色，并且仅有一条有向边从黑点指向白点。此时无论开局选择染哪个点，总能在第二轮把全图染成白色而获胜。

其他情况即为二人平局。注意多测清空！

1
#include <bits/stdc++.h>
2
#define N 100010
3
#define M 200010
4
using namespace std;
5

6
struct Edge {
7
    int to, ne;
8
} edges[M], dag[M];
9

10
int h[N], hs[N], idx = 0, idx1 = 0;
11
int scc_cnt = 0, dfs_cnt = 0;
12
int dfn[N], low[N];
13
int scc_id[N];
14
vector<int> scc[N];
15
stack<int> stk;
16
bool st[N];
17
bool in_stk[N];
18
bool color[N], scc_color[N];
19
int deg[N];
20

21
void add(int u, int v) {
22
    // 建原图
23
    idx++;
24
    edges[idx].to = v;
25
    edges[idx].ne = h[u];
26
    h[u] = idx;
27
}
28

29
void shrink(int u, int v) {
30
    // 建缩点后的图
31
    idx1++;
32
    dag[idx1].to = v;
33
    dag[idx1].ne = hs[u];
34
    hs[u] = idx1;
35
}
36

37
bool tarjan(int u) {
38
    stk.push(u);
39
    in_stk[u] = true;
40
    dfn[u] = low[u] = ++dfs_cnt;
41

42
    for (int i = h[u]; ~i; i = edges[i].ne) {
43
        int j = edges[i].to;
44
        if (!dfn[j]) {
45
            tarjan(j);
46
            low[u] = min(low[u], low[j]);
47
        } else if (in_stk[j]) {
48
            low[u] = min(low[u], dfn[j]);
49
        }
50
    }
51
    if (dfn[u] == low[u]) {
52
        scc_cnt++;
53
        int t;
54
        do {
55
            t = stk.top();
56
            stk.pop();
57
            in_stk[t] = false;
58
            scc_id[t] = scc_cnt;       // 每个点对应的 SCC 编号
59
            scc[scc_cnt].push_back(t); // 维护 SCC 内的节点
60
        } while (t != u);
61
        // 如果同一个 SCC 内存在异色节点，即为无解（平局）
62
        for (int i = 1; i < scc[scc_cnt].size(); i++) {
63
            if (color[scc[scc_cnt][i]] ^ color[scc[scc_cnt][i - 1]]) return false;
64
        }
65
        scc_color[scc_cnt] = color[scc[scc_cnt][0]]; // 同色，给 SCC 染色
66
    }
67
    return true;
68
}
69

70
void init() {
71
    idx = 0;
72
    idx1 = 0;
73
    while (!stk.empty()) stk.pop();
74
    for (int i = 1; i <= scc_cnt; i++) scc[i].clear();
75
    scc_cnt = dfs_cnt = 0;
76
    memset(st, false, sizeof st);
77
    memset(scc_id, 0, sizeof scc_id);
78
    memset(dfn, 0, sizeof dfn);
79
    memset(low, 0, sizeof low);
80
    memset(in_stk, false, sizeof in_stk);
81
    memset(deg, 0, sizeof deg);
82
    memset(h, -1, sizeof h);
83
    memset(hs, -1, sizeof hs);
84
}
85

86
int getFirstBlack() {
87
    // 拓扑排序找出第一个黑色 SCC
88
    queue<int> topo;
89
    for (int i = 1; i <= scc_cnt; i++) {
90
        if (!deg[i]) topo.push(i);
91
    }
92
    while (!topo.empty()) {
93
        int t = topo.front();
94
        topo.pop();
95
        if (scc_color[t]) return t;
96
        for (int i = hs[t]; ~i; i = dag[i].ne) {
97
            int j = dag[i].to;
98
            if (--deg[j] == 0) topo.push(j);
99
        }
100
    }
101
    return 0;
102
}
103

104
bool dfs(int u) {
105
    // 检查黑色子树中是否混有白色 SCC
106
    bool ret = scc_color[u];
107
    st[u] = true;
108
    for (int i = hs[u]; ~i; i = dag[i].ne) {
109
        int j = dag[i].to;
110
        if (st[j]) continue;
111
        ret &= dfs(j);
112
    }
113
    return ret;
114
}
115

116
bool check() {
117
    for (int i = 1; i <= scc_cnt; i++) {
118
        if (scc_color[i] && !st[i]) return false; // 子树必须包含新图中所有的黑色 SCC
119
    }
120
    return true;
121
}
122

123
int main() {
124
    ios::sync_with_stdio(false);
125
    cin.tie(nullptr);
126
    cout.tie(nullptr);
127

128
    int t, m, n;
129
    cin >> t;
130
    while (t--) {
131
        init();
132
        cin >> n >> m;
133
        for (int i = 1; i <= n; i++) cin >> color[i];
134
        int u, v;
135
        for (int i = 1; i <= m; i++) {
136
            cin >> u >> v;
137
            add(u, v);
138
        }
139
        bool tmp = true;
140
        for (int i = 1; i <= n; i++) {
141
            if (!dfn[i]) {
142
                if (!tarjan(i)) {
143
                    tmp = false;
144
                    cout << 'N';
145
                    break;
146
                }
147
            }
148
        }
149
        if (!tmp) continue; // 同 SCC 存在异色节点，直接判无解（平局）
150
        bool b2w = true;
151
        for (int i = 1; i <= scc_cnt; i++) {
152
            for (int a: scc[i]) {
153
                for (int j = h[a]; ~j; j = edges[j].ne) {
154
                    int k = edges[j].to;
155
                    if (scc_id[a] != scc_id[k]) {
156
                        // 缩点建图
157
                        shrink(scc_id[a], scc_id[k]);
158
                        b2w &= !scc_color[scc_id[k]] && scc_color[scc_id[a]]; // 存在一黑一白，检查是否是黑点指向白点
159
                        deg[scc_id[k]]++; // 维护入度
160
                    }
161
                }
162
            }
163
        }
164
        int start = getFirstBlack();
165
        if (dfs(start) && check()) cout << 'A'; // Alice
166
        else if (!start && !color[1]) cout << 'B'; // Bob 情况1
167
        else if (scc_cnt == 2 && scc_color[1] & scc_color[2]) cout << 'B'; // Bob 情况2
168
        else if (scc_cnt == 2 && b2w) cout << 'B'; // Bob 情况3
169
        else cout << 'N';
170
    }
171
    return 0;
172
}

音乐

音乐

文章分享

评论区

音乐

目录

音乐

音乐

P9220 [TAOI-1] - 椎名真昼 题解

文章分享

评论区

音乐

目录

P9220 [TAOI-1] - 椎名真昼题解