#P18644. Jewel Game
Jewel Game
Jewel Game
题目描述
给定一张有 个顶点、 条边的有向图。顶点编号为 ,边编号为 。第 条边从顶点 指向顶点 。图中可能有自环,但没有重边;保证每个顶点至少有一条出边。
图中的一些顶点上共放有 颗珠宝。第 颗珠宝位于顶点 ,价值为 。
Alice 和 Bob 在这张图上进行游戏。初始时,Alice 位于顶点 ,Bob 位于顶点 。两人从 Alice 开始交替执行以下操作:
选择一条从自己当前所在顶点出发的边,沿着这条边移动到它指向的顶点。如果到达的顶点上有珠宝,则取得这颗珠宝,并将它从图上移除。
两枚棋子可以位于同一个顶点,彼此不阻挡移动。初始位置 与 也可以相同。
满足以下任意条件时,游戏结束:
- 所有珠宝都已被取得。
- 当前游戏状态曾经出现过。这里的状态由当前轮到谁行动、两名玩家各自的位置、剩余的珠宝集合共同确定。
游戏结束时,分数定义为:
Alice 希望分数尽可能大,Bob 希望分数尽可能小。求双方都采用最优策略时的最终分数。
输入格式
N M A B
U_1 V_1
...
U_M V_M
K
X_1 W_1
...
X_K W_K
输入仅包含一组数据,所有数均为整数。
输出格式
输出一个整数,表示双方最优行动时的最终分数。
数据范围
- 。
- 。
- 。
- 对任意 ,。
- 对每个顶点 ,至少存在一条边满足 。
- 。
- 。
- 对每个 ,。
- 。
每点出度至少1且无重边,因此 。
样例输入 1
5 16 1 1
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 2
3 4
3 5
4 2
4 3
4 5
5 2
5 3
5 4
4
2 4
3 84
4 38
5 96
样例输出 1
46
样例输入 2
8 16 8 4
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
1 5
2 6
3 7
4 8
5 1
6 2
7 3
8 4
6
1 29
2 34
3 41
5 7
6 26
7 94
样例输出 2
-23