故事
在日本桥王国里,有很多“冰淇淋树”。这里有两种著名的口味:传统香草和热情草莓。 这个国家的人们更看重口味组合的多样性,而不是冰淇淋的总量。
王国是一个有顶点和边的图。这些顶点代表冰淇淋树或冰淇淋店。 作为一名冰淇淋制造商,您可以在该图表中移动,从树上收获口味并将其堆放在您的甜筒上,然后将完成的冰淇淋运送到商店。
商店的满意度取决于其库存的多样性——有多少种不同的口味组合。 现在,所有商店都空无一人。你的任务是最大限度地提高所有冰淇淋店的总体满意度,让王国再次充满活力。
问题陈述
有一个连通无向图 N 顶点和 M 边缘。顶点已编号 0, 1, \ldots, N-1。的 i第一条边连接顶点 A_i 和顶点 B_i.
每个顶点都是以下两种类型之一:
- 冰淇淋店:顶点 0, 1, \ldots, K-1 (K 顶点总数)。
- 冰淇淋树:顶点 K, K+1, \ldots, N-1 (N-K 顶点总数)。
每棵冰淇淋树都提供特定的口味:香草(W = 白色)或草莓色(R = 红色)。最初,所有冰淇淋树都提供香草(W).
你从顶点开始 0 (一家冰淇淋店)和一个空锥体(用空字符串表示)。您最多可以执行 T 步骤。在每个步骤中,选择以下两个操作之一:
- 操作 1:从当前顶点移动到相邻顶点 v。然后,根据类型 v,要么收获冰淇淋,要么送货。
- If v 是一棵冰淇淋树:收获当前口味(
WorR)从那棵树并将其添加到圆锥体字符串的末尾。 - If v 是一家冰淇淋店:将甜筒上当前的口味串添加到商店的库存集中 S_v。然后,你的锥体就变空了。您可以传递一个空字符串;在这种情况下,空字符串将添加到库存集中 S_v.
- 限制:你无法移回到上一个动作 1 中刚刚来自的顶点。具体来说,如果您的最后一个操作 1 是从顶点移动 a 到顶点 b,你的下一个动作 1 不能从 b 返回 a (即使您在中间执行了操作 2)。
- If v 是一棵冰淇淋树:收获当前口味(
- 操作 2:只有当您当前位置是普通位置(
W)冰淇淋树。通过添加草莓汁,从这棵树上收获的味道会变成草莓味(R)为所有未来的收获。你无法将草莓树变回香草树。
如输入生成中所述,该图是 2 边连接的,因此操作 1 始终是可能的。
最大化库存集的大小 S_v 每个冰淇淋店 v。 请注意,传递的字符串已经存在于 S_v 不会增加集合的大小。
评分
您的分数是库存组大小的总和 S_i 遍及所有冰淇淋店 i (0 \le i \lt K): \sum_{i=0}^{K-1} |S_i|
如果产生以下无效输出,则判断为 WA.
- 当当前顶点不是普通顶点时,您执行操作 2 (
W)冰淇淋树。 - 在操作 1 中,您指定一个未通过边直接连接到当前顶点的顶点。
- 在动作 1 中(从第二次开始),您移动到上一个动作 1 中离开的顶点。
- 操作总数超过 T.
有150个测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出:
N M K T
A_{0} B_{0}
\vdots
A_{M-1} B_{M-1}
X_{0} Y_{0}
\vdots
X_{N-1} Y_{N-1}
- 第一行包含四个整数 N, M, K, T。它们分别代表顶点数、边数、冰淇淋店数和最大动作数。这些值满足 N = 100, K = 10,和 T = 10000。对于价值 M,请参阅“输入生成”部分。
- 以下 M 线提供有关边缘的信息。边缘 i 双向连接顶点 A_i 和顶点 B_i.
- 以下 N 线提供坐标 每个顶点的 (X_i,Y_i) 每个顶点的 i 在输入生成期间使用。这些坐标是满足的整数 0 \leq X_i, Y_i \leq 300 和 (X_i, Y_i) \neq (X_j, Y_j) 对于任何 i \neq j。 如果不需要,您可以跳过阅读它们。
输出
输出 T 或更少的行,格式如下:
- 执行操作 1:输出顶点索引 目的地的 v 。
v
- 执行操作 2:输出
-1.
-1
输入生成
让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。
- 对于每个顶点 i,坐标 (X_i,Y_i) 被选择为 X_i = \mathrm{rand}(0, 300), Y_i = \mathrm{rand}(0, 300)。如果到任何已生成顶点的欧几里德距离为 20 或更少,则重新选择坐标。重复这个过程 N 次获取顶点集 V.
- 计算 Delaunay 三角测量 为顶点集 V,并让所得的边集为 E.
- 随机打乱 E,并按顺序对每条边执行以下操作:
- 如果删除边保留图形 (V,E) 2 边连接且无铰接点,从 E 的概率为 0.7.
- 该套 E 处理后所有边都成为图的边集。
工具(输入生成器和可视化工具)
- 网页版:这个比本地版本更强大,提供动画。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。