#PQJ473x432. QOJ 473_432
QOJ 473_432
1 染色游戏 1.1 题目描述 Alice 和Bob 在玩一个染色游戏。游戏在一张N 个点M(N −1 ≤M ≤N) 条边的连通图 上进行,Bob 想要围住Alice,而Alice 想要逃出Bob 的包围。 游戏开始时,Alice 将1 号点涂成了黑色表示占领了1 号点,Bob 将点集S 中的所有点涂 成了白色表示占领了这|S| 个点,保证1 不在S 中。接下来两个人轮流进行操作,由Alice 先 手,每轮中轮到的玩家可以从一个被自己占领的点出发(对于Alice 为黑色点对于Bob 为白色 点),选择一个相邻且未被染色的点,占领该点并染上自己的颜色。如果不存在可以染色的点, 那么这位玩家必须跳过这个回合。当所有点都被染完色时,游戏结束。 Alice 和Bob 约定了一个图中的非空点集T,如果游戏结束时T 中的点全都涂成白色,则 代表Bob 成功围住了Alice,Bob 获胜。反之一定存在一个T 中的点被涂成黑色,那么Alice 获胜。注意这里的T 可能会包含S 中的点和1 号点。 Alice 和Bob 都会使用最优策略。Bob 注意到,在有些局面下,Alice 优势很大,如果能 让Alice 主动跳过Alice 的一些行动回合来获得一个更加公平的局面,这个游戏会更有可玩性。 Bob 想知道,如果Alice 跳过前k 个回合之后自己能够获胜,那么这个k 的最小值是多少。 Alice 只会跳过Alice 的前k 个回合,并且在剩下的回合中采用最优策略,即你可以理解为Bob 在Alice 的第一回合行动之前额外行动了k 个回合。注意如果Bob 在Alice 跳过的一个回合中 没有合法行动,那么Bob 仍需按照规则跳过自己的回合。如果在原图上就是Bob 获胜那么输 出0。如果k = 1000000 时Bob 也不能取胜,则输出1000000。 由于这个图可能很大,我们用如下的方式生成。 • 首先生成一个含有标号为1 到n 一共n 个点的空图。 • 接下来加入m 条链,第i 条链记作(ui, vi, li),其中1 ≤ui, vi ≤n 且ui̸ = vi。 – 首先我们加入li 个点,记作xi 1, xi 2, . . . , xi li。 – 然后在(ui, xi 1), (xi 1, xi 2), (xi 2, xi 3), . . . , (xi li−1, xi li), (xi li, vi) 之间连上无向边。 – 在这次操作之后,本轮中新加入的li 个点不会再与其他的点之间连边,即不同的链 中的xi 1 . . . xi li 均为互不相同的点。特别地,如果l = 0,那么就不添加新点,直接在 (ui, vi) 之间连上无向边。 保证S 集合以及T 集合的点均为一开始生成的n 个点之一。 1.2 输入格式 第一行输入一个整数C,表示数据组数。 对于每组数据: • 第一行输入四个整数n, m, |S|, |T|(1 ≤|S| ≤n −1, 1 ≤|T| ≤n, n −1 ≤m ≤n)。 • 接下来m 行每行输入3 个非负整数ui, vi, li(1 ≤ui, vi ≤n, 0 ≤li ≤106),表示题面中的 第i 条链。 2
• 接下来一行输入|S| 个数s1 . . . s|S| 表示S 集合中的所有元素(2 ≤si ≤n 且不重复)。 • 接下来一行输入|T| 个数t1 . . . t|T| 表示T 集合中的所有元素(1 ≤ti ≤n 且不重复)。 即每组数据按照如下格式输入: n m |S| |T| u1 v1 l1 u2 v2 l2 · · · um vm lm s1 s2 · · · s|S| t1 t2 · · · t|T| 保证ui̸ = vi(即没有自环),保证没有相同的(ui, vi) 对(即没有重边),保证给出的图是 一个连通图。 1.3 输出格式 输出T 行,对于每组测试数据,输出为了让Bob 取胜Alice 至少要跳过的回合数k。如果 在原图上就是Bob 获胜那么输出0。如果k = 1000000 时Bob 也不能取胜,则输出1000000。 1.4 样例输入1 5 6 5 2 2 1 2 0 2 3 0 2 4 0 3 5 0 4 6 0 5 6 3 4 6 5 2 2 1 2 1 2 3 0 2 4 0 3 5 0 4 6 0 5 6 3 4 5 4 2 2 1 2 1 1 3 1 2 4 0 3 5 0 3
4 5 2 3 8 8 1 2 1 2 2 2 3 1 3 4 0 4 5 0 5 6 0 6 7 0 7 2 1 5 8 0 8 3 7 8 8 1 2 1 2 3 2 3 0 3 4 0 4 5 0 5 6 0 6 7 0 7 2 0 5 8 0 8 3 7 1.5 样例输出1 1 0 0 0 1 1.6 样例输入输出2 见下发文件 4
1.7 数据范围与约定 测试点 n m 其他约定 1 无 =n −1 图为一条链 2 无 3 ≤12 =n −1 或n li = 0 4 5 无 6 7 =5 =n 无 8 =6 9 =8 10 无 图为一个环 11 环上一定存在至少两个白色点即|S| 中的点 12 环上一定存在至少一个白色点即|S| 中的点 13 环上一定存在至少一个|T| 中的点 14 15 =n −1 或n |T| = 1 16 |S| = 1 17 18 无 19 20 对于100% 的数据,m = n 或n −1,3 ≤n ≤500,C = 10000,0 ≤li ≤106,1 ≤|S| ≤ n −1, 1 ≤|T| ≤n 且保证图中不存在点数(只计算前n 个点的数量)大于100 的环,每个测试 点中最多只有10 组数据满足n > 50,最多只有1000 组数据满足n > 20。 5