P9220 「TAOI-1」椎名真昼
考点:博弈论、拓扑、强连通分量。
难度: 提高+/省选- 。
题意:
Alice 和 Bob 玩游戏,给定一个有向图,每个点有初始颜色(黑/白)。
双方轮番操作一次,Alice 先手,每次操作选定一个结点,从这个点开始,能到达的点(包含自身)颜色翻转。如果某次操作后所有结点皆为白色,进行该次操作的人获胜。
假设双方都采用策略使得自己胜利,或者如果自己无法胜利,使得对方无法胜利。
给定节点的初始值,求出最终的胜者,亦或者,没有胜者。
n n n 个点, n ≤ 1 0 5 n \le 10^5 n≤105, m m m 条边, m ≤ 2 × 1 0 5 m \le 2 \times 10^5 m≤2×105,T 组数组, T ≤ 15 T \le 15 T≤15。
分析:
经典的 博弈类型 问题。
首先,如果这个游戏无法在两步及以内结束的话,就可以直接算 平局 了。因为若是超过两步,认为自己会输的那一方将会想尽办法不让你赢,具体表现就是重复另一方先前的操作,让图变为另一方操作前的状态,最终陷入死循环。因此我们 只需关注一步定胜负和两步定胜负 的情况。
根据题目中对两点能互相到达的定义,我们很容易知道 – 若对某个 SCC 中的点进行一次操作,那么同处于这个 SCC 的其他点的颜色也都会翻转(但不止这些点的颜色被翻转)。这启发我们处理出原图中的所有强连通分量。
平局:此时不难发现,如果某个 SCC 中存在异色点,那么无论怎么翻转,它们都不会变为统一颜色,于是这种情况可以直接判成平局,否则我们就把这个强连通分量染成内部点的颜色。
缩点:处理出所有的强连通分量后,我们再把一个强连通分量整体看作一个新点,建在新图上(即缩点),此时新图必定是一个有向无环图 DAG。那么如果在某个强连通分量中的某个点上进行操作,新图中该强连通分量的子节点一定也会受到影响从而变化颜色。至此我们便理清了操作与颜色翻转之间的规律。
必胜:因为游戏不会超过两轮,而且先手的 Alice 想要获胜,她就必须在第一轮胜利,否则要么 Bob 胜、要么平局。也因此,在新建的有向无环图上,有且 仅能存在一个节点(黑色节点为根),使得它的子树包含新图中所有的黑色 SCC,且不包含任何白色 SCC。这样一来先手 Alice 才能一次把这些黑色点转化成白色从而获胜。如果这个子树不完全是黑色 SCC,或者是存在多个节点满足要求,都不能保证 Alice 获胜(但也不代表必输,因为还存在平局)。
再来看 Bob 这边,他如果想要获胜,就只能抓住第二轮这唯一的机会。有三种可能性:
- 全图均为白色节点。这样 Alice 只能选择白色节点染黑,此时 Bob 只需重复她的操作即可恢复全图到全白的状态。
- 仅有两个孤立的黑色 SCC。此时 Alice 选择其一染白,Bob 仅需染白另一个即可。
- 一个白色 SCC 和一个黑色 SCC,并且仅有一条有向边从黑点指向白点。此时无论 Alice 开局选择染哪个点,Bob 总能在第二轮把全图染成白色而获胜。
其他情况即为二人平局。
参考代码:
#include <bits/stdc++.h>
#define ll long longconst int N = 100010, M = 200010;
// 原图、缩点后新图边集数组
int h1[N], h2[N], tot1, tot2;
int ne1[M], ne2[M], to1[M], to2[M];
// scc 个数、dfs_cnt = dfn序的结点编号
int scc_cnt = 0, dfs_cnt = 0;
int dfn[N], low[N]; // tarjan()
int scc_id[N];
std::vector<int> scc[N]; // scc 缩点编号
std::stack<int> stk; // 栈
bool st[N];
bool in_stk[N]; // 压栈 scc
bool color[N], scc_color[N]; // 颜色, scc 缩点新图颜色
int deg[N]; // topo 入度数组void add_edge(int u, int v)
{to1[tot1] = v, ne1[tot1] = h1[u], h1[u] = tot1++;
}void add_scc_edge(int u, int v)
{to2[tot2] = v, ne2[tot2] = h2[u], h2[u] = tot2++;
}void init()
{tot1 = tot2 = 0;while (!stk.empty())stk.pop();for (int i = 1; i <= scc_cnt; i++)scc[i].clear();scc_cnt = dfs_cnt = 0;memset(h1, -1, sizeof h1), memset(h2, -1, sizeof h2);memset(st, false, sizeof st), memset(scc_id, 0, sizeof scc_id);memset(dfn, 0, sizeof dfn), memset(low, 0, sizeof low);memset(in_stk, false, sizeof in_stk), memset(deg, 0, sizeof deg);memset(to1, 0, sizeof to1), memset(to2, 0, sizeof to2);memset(ne1, 0, sizeof ne1), memset(ne2, 0, sizeof ne2);
}bool tarjan(int u)
{low[u] = dfn[u] = ++dfs_cnt; // 盖戳、进栈stk.push(u), in_stk[u] = true;for (int i = h1[u]; ~i; i = ne1[i]){int v = to1[i];if (!dfn[v]){tarjan(v);low[u] = std::min(low[v], low[u]);}else if (in_stk[v])low[u] = std::min(low[u], dfn[v]);}if (dfn[u] == low[u]){scc_cnt++; // 连通分量scc个数增加int t;do{t = stk.top();stk.pop();in_stk[t] = false; // 取消标记scc_id[t] = scc_cnt; // 每个点对应的 scc 编号scc[scc_cnt].push_back(t); // 维护 scc 点集} while (t != u);// 如存在 scc 内异色点,即无解(平局) - 打个擂台,判不同for (int i = 1; i < scc[scc_cnt].size(); i++)if (color[scc[scc_cnt][i]] ^ color[scc[scc_cnt][i - 1]])return false;scc_color[scc_cnt] = color[scc[scc_cnt][0]]; // 同色,给 scc 染色}return true;
}// topo 找 DAG 上第一个黑色 scc
int getFirstBlack()
{std::queue<int> q;for (int i = 1; i <= scc_cnt; i++)if (!deg[i])q.push(i);while (q.size()){int u = q.front();q.pop();if (scc_color[u])return u; // 首个黑色for (int i = h2[u]; ~i; i = ne2[i]){int v = to2[i];if (--deg[v] == 0)q.push(v);}}return 0; // 找不到返回 0 说明不存在黑色点
}// 检查以黑色点 u 为根的子树中是否有混有白色
bool dfs(int u)
{bool ret = scc_color[u]; // 取点颜色st[u] = true; // 标记该点已访问for (int i = h2[u]; ~i; i = ne2[i]){int v = to2[i];if (st[v])continue;ret &= dfs(v);}return ret;
}// 检测 scc 集,是否只包含黑色 scc
bool check()
{for (int i = 1; i <= scc_cnt; i++)if (scc_color[i] && !st[i]) // 子树必须包含新图的所有黑色 sccreturn false;return true;
}int main()
{std::ios::sync_with_stdio(false), std::cin.tie(nullptr);int t, m, n;std::cin >> t;while (t--){init();std::cin >> n >> m;for (int i = 1; i <= n; i++)std::cin >> color[i];for (int i = 1, u, v; i <= m; i++)std::cin >> u >> v, add_edge(u, v); // 有向图// std::cout << n << " " << m << std::endl;// 平局bool flag = true;for (int i = 1; i <= n; i++)if (!dfn[i])if (!tarjan(i)){flag = false; // scc 中存在异色结点,判无解(平局)std::cout << "N";break;}if (!flag)continue;bool flag_3 = true; // Bob 情况3: 一白一黑,且黑->白for (int i = 1; i <= scc_cnt; i++){for (int u : scc[i]){for (int j = h1[u]; ~j; j = ne1[j]){int v = to1[j];if (scc_id[u] != scc_id[v]){add_scc_edge(scc_id[u], scc_id[v]); // 缩点建图flag_3 &= !scc_color[scc_id[v]] && scc_color[scc_id[u]]; // 存在一黑一白,检查是否是黑点指向白点( bob 情况 3 判断) 1->0(必须 黑->白 可以画图理解)deg[scc_id[v]]++; // scc 入度++}}}}int start = getFirstBlack();if (dfs(start) && check()) // Alicestd::cout << "A";else if (!start && !color[1])std::cout << "B";else if (scc_cnt == 2 && scc_color[1] & scc_color[2])std::cout << "B";else if (scc_cnt == 2 && flag_3)std::cout << "B";elsestd::cout << "N";}return 0;
}
本文分析参考 链接 然后自建图分析。