U149134 【Minecraft: Story Mode 模拟赛 DLC (1) T1】传送门

> *“That glow... that enchantment is the work of a very old group of builders, a group so old that they existed even before the Order of the Stone!... You see, if these builders truly existed, and if you found their temple... that means we're one step closer to finding... 'The Eversource!' What a beautiful sight!"* > > —Ivor explaining about the Old Builders.

杰西一行人进入了传送门网络（下文简写为「网络」），去寻找传说中的「永恒力量」（The Eversource），却发现昔日宏伟的网络如今早已破败不堪，亟待修复。 通过阅读墙上的说明，杰西得知这个网络本来设有若干个传送门和若干个连接传送门之间的穿梭设施。穿梭设施可以使得一个人仅用 $1$ 秒时间从一个传送门位移到另一个传送门。如果把传送门看成节点，把穿梭设施看成边，则这个网络可以被抽象成一个**不带权的简单无向图**。 由于时间的侵蚀，大部分传送门和所有穿梭设施早已损坏，只剩下 $1$ 号，$2$ 号两座传送门仍然矗立着。 传送门网络的设计十分精妙： (1) 由于传送门的建设十分耗材，所以原网络的**传送门数量不大于 $1000$**。但是**穿梭设施不耗材**，可以随便建造。 (2) **$1$ 号传送门是这个网络的起点**，而古老建筑者们的家在 $2$ 号传送门后。相传，古老建筑者们为了快速回家，在建设传送门网络时，特地让 $1$ 号传送门到 $2$ 号传送门的最短路数量**严格等于** $k$。 只要设计出的传送门网络满足以上两条性质，那么传送门网络就会被重新激活。 艾弗知道，永恒力量就在 $2$ 号传送门后。杰西一行人物资紧缺，为了到达 $2$ 号传送门，杰西一行人希望建造尽量少的传送门，来激活传送门网络。 ### 「一句话」题意 构造一个简单无向图，使得 $1$ 号点与 $2$ 号点之间的最短路数量严格等于 $k$，且点数尽量少。

一行 $6$ 个正整数 $k, n_{5}, n_{4}, \cdots, n_{1}$。$k$ 的含义见题目描述。$n_{5}, n_{4}, \cdots, n_{1}$ 的含义见下文。

第一行两个正整数 $N, M$，表示**新的网络的传送门个数**（不是建造的传送门的个数！）和使用的穿梭设施的个数。必须满足 $N \leq 1000$。 接下来 $M$ 行，每行两个整数 $x, y$，表示存在一个连接了 $x$ 号传送门和 $y$ 号传送门的穿梭设施。 保证合法的解存在，若有多解，输出任意解均可。

**样例解释** 样例输出的网络如图所示： 可以轻易看出， $1$ 号传送门到 $2$ 号传送门的最短路径长度为 $2$，共有 $2$ 条。（$1-3-2$ 与 $1-4-2$） **数据范围** 对于 $100\%$ 的数据，$k \leq 10^9, n_{1} \leq 1000$，$\forall i \in [1,4], n_{i+1} \leq n_{i}$。完整的数据范围详见下表。**对于测试点 $13 \sim 20$，满足 $k \geq 6 \times 10^8$**。 | 测试点 | $k$ | 特殊性质 | 测试点 | $k$ | 特殊性质 | | ------ | ----- | --------------- | ------ | ---- | --------------- | | 1 | $=2$ | 无 | 11 | - | $k$ 是 2 的次幂 | | 2 | $=3$ | 无 | 12 | - | $k$ 是 2 的次幂 | | 3 | $=4$ | 无 | 13 | - | 无 | | 4 | $=5$ | 无 | 14 | - | 无 | | 5 | $=6$ | 无 | 15 | - | 无 | | 6 | $=9$ | 无 | 16 | - | 无 | | 7 | $=10$ | 无 | 17 | - | 无 | | 8 | - | $k$ 是 2 的次幂 | 18 | - | 无 | | 9 | - | $k$ 是 2 的次幂 | 19 | - | 无 | | 10 | - | $k$ 是 2 的次幂 | 20 | - | 无 | **评分标准** 设你建造的网络中， $1$ 号传送门到 $2$ 号传送门的最短路径数为 $K$。若你的输出满足： * $K \neq k$ * $N > 1000$ * 网络中有自环，重边。 * 输出不合法。 则该测试点得 $0$ 分。 否则，若存在 $1 \leq i \leq 5$，使得 $N \leq n_i$，则该测试点得 $i$ 分。若有多个 $i$ 满足条件，取最大的 $i$。 各个测试点的 $n_i$ 见下表： | 测试点编号 | $n_5$ | $n_4$ | $n_3$ | $n_2$ | $n_1$ | | ---------- | ----- | ----- | ----- | ----- | ----- | | 1~7 | 50 | 150 | 350 | 600 | 1000 | | 8~12 | 170 | 250 | 450 | 750 | 1000 | | 13 | 650 | 720 | 775 | 875 | 1000 | | 14 | 400 | 500 | 700 | 775 | 950 | | 15 | 300 | 400 | 500 | 700 | 850 | | 16 | 250 | 300 | 375 | 500 | 750 | | 17 | 220 | 300 | 350 | 400 | 650 | | 18 | 200 | 250 | 300 | 320 | 500 | | 19 | 165 | 210 | 240 | 270 | 400 | | 20 | 165 | 190 | 225 | 250 | 300 | **luogu SPJ 返回信息解释** ```Too many portals required - limit: 1000, requirement: %d.```：$n$ 太大。 ```Invalid quantum transportation device(QTD) detected - out of range - QTD #%d (%d, %d).```：这条边范围错误，节点编号 $> n$ 或 $< 1$。 ```Invalid quantum transportation device(QTD) detected - self-loop - QTD #%d (%d, %d).```：自环 ```Invalid quantum transportation device(QTD) detected - duplicated - QTD #%d (%d, %d).```：重边 ```Invalid scheme - shortest path between 1 & 2: %d. %d paths detected, but expected %d paths.```：方案错 ```Imperfect scheme - %d portal used, scored %d pts.```：方案正确，部分分 ```Correct scheme - %d portals used.```：方案正确，全分。 **致谢 & 相关信息** 灵感来源：省中 2019 年提高组模拟赛 Inspiration: Simulation contest in SCZ in 2019 原出题人：徐翊轩 Original Problemsetter: Yixuan Xu 数据、标程：fsy\_juruo Data & std: fsy\_juruo 审题、验题：[@赤司征十郎](https://www.luogu.com.cn/user/74037) Verification: [@赤司征十郎](https://www.luogu.com.cn/user/74037) 题目背景：*Minecraft: Story Mode* 第一季 第五章 Problem Background: *Minecraft: Story Mode* Season I, Episode 5: “Order Up!”