AT_ahc060_a.[AHC060A] Ice Cream Collection

有一个联通的无向图，包含 $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$ 的类型，要么采集冰淇淋，要么交付冰淇淋。
  • 如果 $v$ 是冰淇淋树：从该树采集当前口味（W 或 R），并将其添加到甜筒字符串的末尾。
  • 如果 $v$ 是冰淇淋店：将你手中甜筒的当前口味字符串加入该店的库存集合 $S_v$。随后你的甜筒将变为空。你可以送交空字符串，此时空字符串也会被加入到库存集合 $S_v$。
  • 限制：你不能返回你上一步刚刚离开的顶点。 具体来说，如果你上一次行动1是从顶点 $a$ 走到顶点 $b$，那么下一次行动1就不能从 $b$ 再走回 $a$（即使中间进行了行动2）。
• 行动2：仅当你当前位置位于香草味（W）的冰淇淋树时才能进行。通过添加草莓汁，该树今后采集出的口味会变为草莓味（R）。不能将草莓味的树再变回香草味。

如输入生成部分所述，图是2-边连通的，因此行动1始终可行。

你需要最大化每家冰淇淋店 $v$ 的库存集合 $S_v$ 的大小。请注意，交付已经在 $S_v$ 中存在的字符串不会增加集合的大小。

输入以如下格式从标准输入给出：

$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$ 行，每行给出顶点 $i$ 的坐标 $(X_i, Y_i)$，这些坐标在输入生成时用到。$0\leq X_i, Y_i \leq 300$，且任意两个顶点 $i\neq j$，都有 $(X_i, Y_i)\neq (X_j, Y_j)$。如果不需要可跳过读取这些坐标。

输出不超过 $T$ 行，每行格式如下：

• 执行动作1时：输出目标顶点的编号 $v$。

$v$

• 执行动作2时：输出 -1。

-1

评分方式

你的得分是所有冰淇淋店库存集合 $S_i$ 的大小之和（$0\leq i < K$）：即 $ \sum_{i=0}^{K-1} |S_i| $。

若输出了以下不合法数据，将判为答案错误（WA）：

• 在当前位置不是香草味（W）的冰淇淋树时执行了行动2。
• 行动1时，指定移动的目标顶点并未与当前位置直接相连。
• 行动1（从第二次起），移动路径回到了上一次行动1的出发顶点。
• 总操作次数超过 $T$。

共150个测试用例。提交代码的总得分为所有测试用例的得分之和。如果你的提交在某些测试用例中输出不合法或超时，则全体提交会被判为WA或TLE，得分为零。比赛期间所得的最高得分将作为最终排名标准，赛后不会有系统测试。同分情况下，参赛者按最后得分并列，不分答题时间。

输入生成

令 $\mathrm{rand}(L,U)$ 表示在区间 $[L,U]$ 内均匀生成一个随机整数。

1. 对每个顶点 $i$，应用 $X_i = \mathrm{rand}(0, 300)$，$Y_i = \mathrm{rand}(0, 300)$。若与已生成的任一顶点欧几里得距离 $\leq 20$ 则重选。重复该过程 $N$ 次完成顶点集 $V$。
2. 计算顶点集 $V$ 的 Delaunay 三角剖分，其边集记为 $E$。
3. 随机打乱边集 $E$，依次对每条边执行如下操作：
   • 如果移除此边后，图 $(V, E)$ 仍是2-边连通且无割点，则以概率 $0.7$ 移除此边。
4. 处理完成产生的边集即为最终图的边集。

工具（输入生成与可视化）

• 网页版：功能较强，支持动画。
• 本地版：需 Rust编程语言 环境。
  • Windows预编译版：若不熟悉Rust环境可用此版本。

请注意：比赛期间禁止分享可视化结果和讨论思路。

由 ChatGPT 5 翻译