← 返回题目列表

AtCoder · ahc060_a

A. 冰淇淋系列

中文机器翻译题面 查看原题

故事

在日本桥王国里,有很多“冰淇淋树”。这里有两种著名的口味:传统香草和热情草莓。 这个国家的人们更看重口味组合的多样性,而不是冰淇淋的总量。

王国是一个有顶点和边的图。这些顶点代表冰淇淋树或冰淇淋店。 作为一名冰淇淋制造商,您可以在该图表中移动,从树上收获口味并将其堆放在您的甜筒上,然后将完成的冰淇淋运送到商店。

商店的满意度取决于其库存的多样性——有多少种不同的口味组合。 现在,所有商店都空无一人。你的任务是最大限度地提高所有冰淇淋店的总体满意度,让王国再次充满活力。

问题陈述

有一个连通无向图 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 是一棵冰淇淋树:收获当前口味(W or R)从那棵树并将其添加到圆锥体字符串的末尾。
    • If v 是一家冰淇淋店:将甜筒上当前的口味串添加到商店的库存集中 S_v。然后,你的锥体就变空了。您可以传递一个空字符串;在这种情况下,空字符串将添加到库存集中 S_v.
    • 限制:你无法移回到上一个动作 1 中刚刚来自的顶点。具体来说,如果您的最后一个操作 1 是从顶点移动 a 到顶点 b,你的下一个动作 1 不能从 b 返回 a (即使您在中间执行了操作 2)。
  • 操作 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,包括在内。

  1. 对于每个顶点 i,坐标 (X_i,Y_i) 被选择为 X_i = \mathrm{rand}(0, 300), Y_i = \mathrm{rand}(0, 300)。如果到任何已生成顶点的欧几里德距离为 20 或更少,则重新选择坐标。重复这个过程 N 次获取顶点集 V.
  2. 计算 Delaunay 三角测量 为顶点集 V,并让所得的边集为 E.
  3. 随机打乱 E,并按顺序对每条边执行以下操作:
    • 如果删除边保留图形 (V,E) 2 边连接且无铰接点,从 E 的概率为 0.7.
  4. 该套 E 处理后所有边都成为图的边集。

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。