P14371 [JOISC 2018] 航空路线图 / Airline Route Map
题目背景
在洛谷上提交时，需要将两个文件合并成一个提交。
**不要引入任何头文件**，并在文件头加入以下内容：
```cpp
void Alice(int N, int M, int A[], int B[] );
void InitG(int V, int U );
void MakeG(int pos, int C, int D );
void Bob(int V, int U, int C[], int D[] );
void InitMap(int N, int M );
void MakeMap(int A, int B );
```
题目描述
Alice 居住在 JOI 王国。她计划邀请居住在 IOI 共和国的 Bob。在邀请他之前，她打算将 JOI 王国的航线地图发送给他。JOI 王国是一个由 $N$ 个岛屿组成的岛国，岛屿编号从 $0$ 到 $N-1$。JOI 王国内共有 $M$ 条航线。对于每个 $i$（$0 \le i \le M-1$），第 $(i+1)$ 条航线连接岛屿 $A_i$ 和岛屿 $B_i$，且为双向航线。任意两条航线不会连接相同的两个岛屿。她必须使用一台由 JOI 王国运营的特殊电报机。她可以通过该电报机发送一个无向图。然而，当她使用它时，顶点编号和边编号会被随机打乱。
具体而言，信息的发送方式如下。设 $G$ 为 Alice 发送的图（令 $V$ 为图 $G$ 的顶点数，$U$ 为图 $G$ 的边数）：
- Alice 指定图 $G$ 的边数 $V$ 和边数 $U$。然后，她将数字 $0, 1, \ldots, V-1$ 分别分配给每个顶点，将数字 $0, 1, \ldots, U-1$ 分别分配给每条边。
- Alice 指定参数 $C_0, C_1, \ldots, C_{U-1}$ 和 $D_0, D_1, \ldots, D_{U-1}$。这些参数描述图 $G$ 的边，即对于每个 $j$（$0 \le j \le U-1$），图 $G$ 的第 $j$ 条边连接顶点 $C_j$ 和顶点 $D_j$。
- 图 $G$ 的顶点编号由 JOI 王国打乱。首先，JOI 王国生成一个序列 $p[0], p[1], \ldots, p[V-1]$，它是 $0, 1, \ldots, V-1$ 的一个排列。然后，$C_0, C_1, \ldots, C_{U-1}$ 被替换为 $p[C_0], p[C_1], \ldots, p[C_{U-1}]$，而 $D_0, D_1, \ldots, D_{U-1}$ 被替换为 $p[D_0], p[D_1], \ldots, p[D_{U-1}]$。
- 接着，图 $G$ 的边编号由 JOI 王国打乱。首先，JOI 王国生成一个序列 $q[0], q[1], \ldots, q[U-1]$，它是 $0, 1, \ldots, U-1$ 的一个排列。然后，$C_0, C_1, \ldots, C_{U-1}$ 被替换为 $C_{q[0]}, C_{q[1]}, \ldots, C_{q[U-1]}$，而 $D_0, D_1, \ldots, D_{U-1}$ 被替换为 $D_{q[0]}, D_{q[1]}, \ldots, D_{q[U-1]}$。
- 以下数据被发送给 Bob：$V$ 和 $U$ 的值，以及参数 $C_0, C_1, \ldots, C_{U-1}$ 和 $D_0, D_1, \ldots, D_{U-1}$ 的最新值。
请注意，使用这台电报机只能发送一个简单图。此处，“简单图”指不含重边和自环的图。
换句话说，她可以发送一个满足以下条件的图：对于任意 $i, j$（$0 \le i < j \le U-1$），$(C_i, D_i) \ne (C_j, D_j)$ 且 $(C_i, D_i) \ne (D_j, C_j)$ 成立；同时，对于任意 $i$（$0 \le i \le U-1$），$C_i \ne D_i$ 成立。
Alice 希望使用顶点数最少的图，将 JOI 王国的航线地图发送给 Bob。
**任务**
为了帮助 Alice 与 Bob 之间的通信，请编写以下两个程序：
- 给定 JOI 王国的岛屿数量 $N$、航线数量 $M$，以及表示 JOI 王国航线地图的序列 $A$、$B$，第一个程序应输出 Alice 发送的图 $G$ 的信息。
- 给定 Bob 收到的图 $G$ 的信息，第二个程序应恢复 JOI 王国的航线地图。
**实现细节**
你需要提交两个文件。
第一个文件为 `Alice.cpp`。该文件应输出 Alice 发送的图的信息。它应实现以下函数。程序应包含头文件 `Alicelib.h`。
- `void Alice( int N, int M, int A[], int B[] )`
对于每个测试用例，该函数被调用一次。
- 参数 $N$ 是 JOI 王国的岛屿数量。
- 参数 $M$ 是 JOI 王国的航线数量。
- 参数 $A[]$、$B[]$ 是长度为 $M$ 的序列，用于描述 JOI 王国的航线地图。
通过以下函数，函数 `Alice` 输出 Alice 发送的图 $G$ 的信息。
- `void InitG( int V, int U )`
该函数指定图 $G$ 的顶点数和边数。
- 参数 $V$ 是图 $G$ 的顶点数。参数 $V$ 应为介于 $1$ 到 $1500$（含）之间的整数。若调用该函数时参数超出此范围，你的程序将被视为 **Wrong Answer [1]**。
- 参数 $U$ 是图 $G$ 的边数。参数 $U$ 应为介于 $0$ 到 $V(V-1)/2$（含）之间的整数。若调用该函数时参数超出此范围，你的程序将被视为 **Wrong Answer [2]**。
- `void MakeG( int pos, int C, int D )`
该函数指定图 $G$ 的边。
- 参数 `pos` 是由本次调用指定的边的编号。参数 `pos` 应为介于 $0$ 到 $U-1$（含）之间的整数。若调用该函数时参数超出此范围，你的程序将被视为 **Wrong Answer [3]**。该函数对相同的参数 `pos` 不应被调用超过一次；若被多次调用，你的程序将被视为 **Wrong Answer [4]**。
- 参数 $C$ 和 $D$ 是图 $G$ 中边 `pos` 的两个顶点。$C$ 和 $D$ 应为介于 $0$ 到 $V-1$（含）之间的整数，且应满足 $C \ne D$。若 $C$ 或 $D$ 不满足这些条件，你的程序将被视为 **Wrong Answer [5]**。此处，$U$ 和 $V$ 是由函数 `InitG` 指定的整数。
在函数 `Alice` 中，调用函数 `InitG` 一次后，函数 `MakeG` 应被恰好调用 $U$ 次。若函数 `InitG` 被调用两次，你的程序将被视为 **Wrong Answer [6]**。若在调用函数 `InitG` 之前调用了函数 `MakeG`，你的程序将被视为 **Wrong Answer [7]**。若在函数 `Alice` 结束时未调用函数 `InitG`，或函数 `MakeG` 未被调用 $U$ 次，你的程序将被视为 **Wrong Answer [8]**。当函数 `Alice` 结束时，若 Alice 描述的图 $G$ 不是一个简单图，你的程序将被视为 **Wrong Answer [9]**。
若对函数 `Alice` 的调用被视为 **Wrong Answer**，你的程序将立即终止。
第二个文件为 `Bob.cpp`。该文件在给定 Bob 收到的图 $G$ 的信息后，输出 JOI 王国的航线地图。它应实现以下函数。程序应包含头文件 `Boblib.h`。
- `void Bob( int V, int U, int C[], int D[] )`
对于每个测试用例，该函数被调用一次。
- 参数 $V$ 是图 $G$ 的顶点数。
- 参数 $U$ 是图 $G$ 的边数。
- 参数 $C[]$、$D[]$ 是长度为 $U$ 的序列，用于描述图 $G$ 的边。
通过以下函数，函数 `Bob` 恢复 JOI 王国的航线地图，并输出航线地图的信息。
- `void InitMap( int N, int M )`
该函数指定 JOI 王国的岛屿数量和航线数量。
- 参数 $N$ 是恢复出的 JOI 王国岛屿数量。$N$ 应为一个整数，且必须等于 JOI 王国实际的岛屿数量。若两者不相等，你的程序将被视为 **Wrong Answer [10]**。
- 参数 $M$ 是恢复出的 JOI 王国航线数量。$M$ 应为一个整数，且必须等于 JOI 王国实际的航线数量。若两者不相等，你的程序将被视为 **Wrong Answer [11]**。
- `void MakeMap( int A, int B )`
该函数指定 JOI 王国的航线数量。
- 参数 $A$ 和 $B$ 表示存在一条连接岛屿 $A$ 与岛屿 $B$ 的航线。$A$ 和 $B$ 应为介于 $0$ 到 $N-1$（含）之间的整数，且应满足 $A \ne B$。若 $A$ 或 $B$ 不满足这些条件，你的程序将被视为 **Wrong Answer [12]**。若在 JOI 王国中不存在连接岛屿 $A$ 与岛屿 $B$ 的航线，你的程序将被视为 **Wrong Answer [13]**。由该函数调用所描述的航线应与之前调用所描述的航线不同。当调用 `MakeMap( A, B )` 时，若此前已调用过 `MakeMap( A, B )` 或 `MakeMap( B, A )`，你的程序将被视为 **Wrong Answer [14]**。
此处，$N$ 是由 `InitMap` 指定的整数值。
在函数 `Bob` 中，调用函数 `InitMap` 一次后，函数 `MakeMap` 应被恰好调用 $M$ 次。若函数 `InitMap` 被调用两次，你的程序将被视为 **Wrong Answer [15]**。若在调用函数 `InitMap` 之前调用了函数 `MakeMap`，你的程序将被视为 **Wrong Answer [16]**。若在函数 `Bob` 结束时未调用函数 `InitMap`，或函数 `MakeMap` 未被调用 $M$ 次，你的程序将被视为 **Wrong Answer [17]**。此处，$M$ 是由 `InitMap` 指定的整数值。
若对函数 `Bob` 的调用被视为 **Wrong Answer**，你的程序将立即终止。
**评分流程**
评分按以下方式进行。若你的程序被视为 **Wrong Answer**，它将立即终止。
（1）调用一次函数 `Alice`，其参数描述 JOI 王国的航线地图信息。
（2）设 $G$ 为由函数 `Alice` 指定的图。调用一次函数 `Bob`，其参数为图 $G$ 的顶点编号的随机重排和边编号的随机重排。
（3）你的程序被评分。
**重要提示**
- 你的程序可以为内部使用实现其他函数，或使用全局变量。提交的文件将与评分器一起编译，并生成一个可执行文件。所有全局变量和内部函数应声明为 `static`，以避免与其他文件冲突。评分时，程序将作为两个独立进程（Alice 进程和 Bob 进程）运行。Alice 进程与 Bob 进程之间不能共享全局变量。
- 你的程序不应使用标准输入和标准输出。你的程序不应通过任何方式与其他文件通信。但，你的程序可以向标准错误输出调试信息。
**编译与测试运行**
你可以从竞赛网页下载一个归档文件，其中包含用于测试你程序的样例评分器。该归档文件还包含你程序的一个样例源代码文件。
样例评分器由一个源文件组成，即 `grader.cpp`。若你的程序为 `Alice.cpp` 和 `Bob.cpp`，为测试它们，你需要将这些文件（`grader.cpp`、`Alice.cpp`、`Bob.cpp`、`Alicelib.h` 和 `Boblib.h`）放入同一目录，并运行以下命令来编译你的程序：
```
g++ -std=c++14 -O2 -o grader grader.cpp Alice.cpp Bob.cpp
```
当编译成功后，将生成可执行文件 `grader`。
请注意，实际评分器与样例评分器不同。样例评分器将以单个进程方式运行，它将从标准输入读取输入数据，并将结果写入标准输出。
输入格式
样例评分器从标准输入读取以下数据。
- 第一行包含两个以空格分隔的整数，表示 JOI 王国由 $N$ 个岛屿组成，且 JOI 王国共有 $M$ 条航线。
- 接下来的 $M$ 行包含航线地图的信息。第 $(i+1)$ 行（其中 $0 \le i \le M-1$）包含两个以空格分隔的整数 $A_i$、$B_i$，它们描述 JOI 王国航线地图的信息。
输出格式
当程序成功终止时，样例评分器将以下信息写入标准输出。（引号本身不会实际输出。）
- 若你的程序被视为 **Wrong Answer**，样例评分器将以如下格式输出其类型：“Wrong Answer [1]”，然后终止。
- 若对函数 `Alice` 和 `Bob` 的调用均未被视为 **Wrong Answer**，样例评分器将输出 “Accepted.”，并同时输出 $V$ 的值。
若你的程序被视为多种类型的 **Wrong Answer**，样例评分器仅报告其中一种。
说明/提示
### 数据范围
所有输入数据满足以下条件：
- $1 \le N \le 1000$。
- $0 \le M \le N(N-1)/2$。
- $0 \le A_i \le N-1$（其中 $0 \le i \le M-1$）。
- $0 \le B_i \le N-1$（其中 $0 \le i \le M-1$）。
- $A_i \ne B_i$（其中 $0 \le i \le M-1$）。
- $(A_i, B_i) \ne (A_j, B_j)$ 且 $(A_i, B_i) \ne (B_j, A_j)$（其中 $0 \le i < j \le M-1$）。
### 子任务
共有 3 个子任务。每个子任务的得分和附加约束如下：
**子任务 1 [22 分]**
- $N \le 10$。
**子任务 2 [15 分]**
- $N \le 40$。
**子任务 3 [63 分]**
无附加约束。
**评分规则**
- 在子任务 1 或子任务 2 中，若你的程序解决了所有测试用例，你将获得满分。
- 在子任务 3 中，若你的程序解决了所有测试用例，你的得分按以下方式计算。令 $ \text{MaxDiff} $ 为 $ V - N $ 的最大值：
- 当 $ 101 \le \text{MaxDiff} $ 时，你的得分为 $ 0 $。
- 当 $ 21 \le \text{MaxDiff} \le 100 $ 时，你的得分为 $ 13 + \left\lfloor \dfrac{100 - \text{MaxDiff}}{4} \right\rfloor $。此处，$ \lfloor x \rfloor $ 表示不超过 $ x $ 的最大整数。
- 当 $ 13 \le \text{MaxDiff} \le 20 $ 时，你的得分为 $ 33 + (20 - \text{MaxDiff}) \times 3 $。
- 当 $ \text{MaxDiff} \le 12 $ 时，你的得分为 $ 63 $。
翻译由 Qwen3-235B 完成