UOJ Logo Universal Online Judge

UOJ

#587. 【ZJOI2020】染色游戏

附件下载 统计

Alice 和 Bob 在玩一个染色游戏。游戏在一张 N 个点 M(N1MN) 条边的连通图上进行,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

由于这个图可能很大,我们用如下的方式生成。

  • 首先生成一个含有标号为 1n 一共 n 个点的空图。
  • 接下来加入 m 条链,第 i 条链记作 (ui,vi,li),其中 1ui,vinuivi
    • 首先我们加入 li 个点,记作 x1i,x2i,,xlii
    • 然后在之 (ui,x1i),(x1i,x2i),(x2i,x3i),,(xli1i,xlii),(xlii,vi) 间连上无向边。
    • 在这次操作之后,本轮中新加入的 li 个点不会再与其他的点之间连边,即不同的链中的 x1ixlii 均为互不相同的点。特别地,如果 l=0,那么就不添加新点,直接在 (ui,vi) 之间连上无向边。

保证 S 集合以及 T 集合的点均为一开始生成的 n 个点之一。

输入格式

第一行输入一个整数 C,表示数据组数。

对于每组数据:

  • 第一行输入四个整数 n,m,|S|,|T|(1|S|n1,1|T|n,n1mn)
  • 接下来 m 行每行输入 3 个非负整数 ui,vi,li(1ui,vin,0li106),表示题面中的第 i 条链。
  • 接下来一行输入 |S| 个数 s1s|S| 表示 S 集合中的所有元素(2sin 且不重复)。
  • 接下来一行输入 |T| 个数 t1t|T| 表示 T 集合中的所有元素(1tin 且不重复)。

即每组数据按照如下格式输入: n m |S| |T|u1 v1 l1u2 v2 l2um vm lms1 s2s|S|t1 t2t|T|

保证 uivi(即没有自环),保证没有相同的 (ui,vi) 对(即没有重边),保证给出的图是 一个连通图。

输出格式

输出 C 行,对于每组测试数据,输出为了让 Bob 取胜 Alice 至少要跳过的回合数 k。如果在原图上就是 Bob 获胜那么输出 0。如果 k=1000000 时 Bob 也不能取胜,则输出 1000000

样例一

input

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
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

output

1
0
0
0
1

样例二

见附加文件中 ex_game2.inex_game2.ans

限制与约定

测试点 n m 其他约定
1 =n1 图为一条链
2
3 12 =n1n li=0
4
5
6
7 =5 =n
8 =6
9 =8
10 图为一个环
11 环上一定存在至少两个白色点即 |S| 中的点
12 环上一定存在至少一个白色点即 |S| 中的点
13 环上一定存在至少一个 |T| 中的点
14 环上一定存在至少一个 |T| 中的点
15 =n1n |T|=1
16 |S|=1
17
18
19
20

对于 100% 的数据,m=nn13n500C=100000li1061|S|n1,1|T|n 且保证图中不存在点数(只计算前 n 个点的数量)大于 100 的环,每个测试点中最多只有 10 组数据满足 n>50,最多只有 1000 组数据满足 n>20

时间限制1s

空间限制512MB

下载

样例数据下载