资源简介

2013 亚太地区信息学奥林匹克竞赛
APIO 2013
竞赛时间：2013 年 5 月 11 日 9:00-14:00
题目名称 机器人 道路费用 出题人
英文名称 ROBOTS TOLL TASKSAUTHOR
输入 标准输入
输出 标准输出
每个测试点时限 1.5 秒 2.5 秒 /
内存限制 128 MB 128MB /
试题总分 100 100 100
测试点数目 20 20 8
每个测试点分值 5 5 见题面
编译器版本及编译选项见考试注意事项。
2013 亚太地区信息学奥林匹克竞赛
机器人
机器人
【问题描述】
VRI（Voltron 机器人学会）的工程师建造了 n 个机器人。任意两个兼容的机
器人站在同一个格子时可以合并为一个复合机器人。
我们把机器人用 1 至 n 编号（n ≤ 9）。如果两个机器人的编号是连续的，那
么它们是兼容的，可以合并成一个复合机器人。最初这 n 个机器人各自都只有唯
一的编号。而一个由两个或以上的机器人合并构成的复合机器人拥有两个编号，
分别是构成它的所有机器人中最小和最大的编号。
例如，2 号机器人只可以与 1 号或 3 号机器人合并。若 2 号机器人与 3 号机
器人合并，可构成编号为 2-3 的复合机器人。如果编号为 2-3 的复合机器人与编
号为 4-6 的复合机器人合并，可构成编号为 2-6 的复合机器人。当所有机器人合
并以后则构成 1-n 复合机器人。
工程师把这 n 个机器人放在了一个封闭的房间中，房间四周均是墙。该房间
被划分成 w × h 个方格。有些方格有障碍物，机器人不可经过或停留；其余方格
允许多个机器人停留，同时允许机器人经过。任何时候一个机器人只占用一个方
格。初始时刻，所有机器人均在不同的方格中。
这些原始的机器人不会自发地移动。它们只有被工程师沿 x 轴或 y 轴推动
后，才会沿推动的方向不断向前直线移动，直至碰到障碍物或墙停止移动。停止
移动后，它会扫描当前的格子是否存在可以与它合并的机器人，如果有，则合并
并继续检查，直至不能再合并为止。工程师只能沿水平向左、水平向右、竖直向
上、竖直向下四个方向推动机器人，并且，在机器人尚未停止移动时，不允许推
动其它机器人，因此任何时刻，房间中都只能有一个机器人移动。
为了帮助机器人转向，工程师在一些格子中放置了转向器。具体地说，转向
器分为顺时针转向器（右转器）和逆时针转向器（左转器），顺时针转向器可以
使到达该格子的机器人沿顺时针方向转向 90°；逆时针转向器可以使到达该格
子的机器人沿逆时针方向转向 90°。
现在，我们将告诉你初始时刻房间内的信息。请你计算工程师最少共计需要
推动机器人多少次，才能把所有的 n 个机器人全部合并（如果可能的话）。
【输入格式】
你的程序必须从标准输入读入。输入的第 1 行包含 3 个整数 n、w 和 h，用
空格隔开。
输入文件中接下来的 h 行描述初始时刻房间内的信息，每行包含 w 个字符。
这 w × h 个字符中每一个表示房间中的一个格子，意义如下：
‘1’至‘9’：表示该方格中有一个机器人，编号为这个数字；
‘x’：表示该方格有障碍物；
‘A’：表示该方格中有一个逆时针转向器；
‘C’：表示该方格中有一个顺时针转向器；
‘.’：表示该方格为空地。
第 2 页 共 11 页
2013 亚太地区信息学奥林匹克竞赛
机器人
【输出格式】
你的程序必须输出到标准输出。输出仅一个整数，表示最少需要推动的次数。
若不能使所有机器人全部合并，输出-1。
【样例输入】
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
【样例输出】
5
【样例说明】
第一步：向右推动 3 号机器人，当它碰到转向器后会向上继续移动，直至碰
到墙壁停止移动。
第二步：向上推动 4 号机器人，当它碰到墙壁后停止移动，与 3 号机器人合
并，构成 3-4 号机器人
第三步：向上推动 2 号机器人，当它碰到转向器后会向左移动，由于左侧为
墙壁，故停留在原地。
第四步：向右推动 2 号机器人，由于它在一个转向器上，故它会向上移动，
直至碰到墙壁停止移动，与 1 号机器人合并，构成 1-2 号机器人。
第五步：向左推动 3-4 号机器人，当它碰到墙壁后停止移动，与 1-2 号机器
人合并，构成 1-4 号机器人。
【数据规模与约定】
我们将使用以下 4 类输入测例测试你的程序。
1. （10 分）测例满足 n = 2，w ≤ 10 且 h ≤ 10，没有任何转向器。
2. （20 分）测例满足 n = 2，w ≤ 10 且 h ≤ 10。
3. （30 分）测例满足 n ≤ 9，w ≤ 300 且 h ≤ 300。
4. （40 分）测例满足 n ≤ 9，w ≤ 500 且 h ≤ 500。
第 3 页 共 11 页
2013 亚太地区信息学奥林匹克竞赛
道路费用
道路费用
【问题描述】
幸福国度可以用 N 个城镇（用 1 到 N 编号）构成的集合来描述，这些城镇
最开始由 M 条双向道路（用 1 到 M 编号）连接。城镇 1 是中央城镇。保证一个
人从城镇 1 出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是
收费道路，道路 i 的使用者必须向道路的主人支付 ci 分钱的费用。已知所有的这
些 ci是互不相等的。最近有K条新道路建成，这些道路都属于亿万富豪Mr. Greedy。
Mr. Greedy 可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣
布这些费用。
两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这
些道路游行并前往中央城镇。共计 pj 个参与者将从城镇 j 出发前往中央城镇。这
些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一
天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就
是 Mr. Greedy。同样根据这个习俗，Mr. Greedy 选出的这个道路集合必须使所有
选出道路的费用之和最小，并且仍要保证任何人可以从城镇 j 前往城镇 1（因此，
这些选出的道路来自将费用作为相应边边权的“最小生成树”）。如果有多个这样
的道路集合，Mr. Greedy 可以选其中的任何一个，只要满足费用和是最小的。
Mr. Greedy 很明确地知道，他从 K 条新道路中获得的收入不只是与费用有
关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果 p
个人经过道路 i，道路 i 产生的收入为 ci p 的积。注意 Mr. Greedy 只能从新道路
收取费用，因为原来的道路都不属于他。
Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收
入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路
（将在嘉年华的前一天公布），使得他在 K 条新道路的收入最大。注意 Mr. Greedy
仍然需要遵循选出花费之和最小的道路集合的习俗。
你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序
来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。
【输入格式】
你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数 N，M 和
K。接下来的 M 行描述最开始的 M 条道路。这 M 行中的第 i 行包含由空格隔开
的整数 ai，bi 和 ci，表示有一条在 ai 和 bi 之间，费用为 ci 的双向道路。接下来的
K 行描述新建的 K 条道路。这 K 行中的第 i 行包含由空格隔开的整数 xi 和 yi，表
示有一条连接城镇 xi 和 yi 新道路。最后一行包含 N 个由空格隔开的整数，其中
的第 j 个为 pj，表示从城镇 j 前往城镇 1 的人数。
输入也满足以下约束条件。
1 ≤ N ≤ 100000；
1 ≤ K ≤ 20；
1 ≤ M ≤ 300000；
6
对每个 i 和 j，1 ≤ ci, pj ≤ 10 ；
第 4 页 共 11 页
2013 亚太地区信息学奥林匹克竞赛
道路费用
如果 i ≠ i'，则 ci ≠ ci'；
在任意两个城市之间，最多只有一条道路（包括新建的道路）。
【输出格式】
你的程序必须输出恰好一个整数到标准输出，表示能获得的最大的收入。
【样例输入】
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
【样例输出】
400
【样例说明】
在样例中，Mr. Greedy 应该将新道路(1,3)的费用设置为 5 分钱。在这个费用
下，他可以选择道路(3,5)，(1,2)，(2,4)和(1,3)来最小化总费用，这个费用为 14。
从城镇 3 出发的 30 个人和从城镇 5 出发的 50 个人将经过新道路前往城镇 1，因
此他可以获得为(30+50)×5=400 分钱的最好收入。
如果我们这样做，将新道路(1,3)的费用设置为 10 分钱。根据传统的限制，
Mr. Greedy 必须选择(3,5)，(1,2)，(2,4)和(2,3)，因为这是唯一费用最小的集合。
因此，在嘉年华的过程中道路(1,3)将没有任何收入。
【数据规模与约定】
我们将使用以下 5 类测例测试你的程序。
1. （国际 16 分，国内 15 分）N ≤ 10，M ≤ 20 且 K = 1；
2. （国际 18 分，国内 20 分）N ≤ 30，M ≤ 50 且 K ≤ 10；
3. （国际 22 分，国内 20 分）N ≤ 1,000，M ≤ 5,000 且 K ≤ 10；
4. （国际 22 分，国内 20 分）N ≤ 100,000，M ≤ 300,000 且 K ≤ 15；
5. （国际 22 分，国内 25 分）N ≤ 100,000，M ≤ 300,000 且 K ≤ 20。
第 5 页 共 11 页
2013 亚太地区信息学奥林匹克竞赛
出题人
出题人
【问题描述】
当今世界上各类程序设计竞赛层出不穷。而设计一场好比赛绝非易事，比如
给题目设计测试数据就是一项挑战。一组好的测试数据需要对不同的程序有区分
度：满足所有要求的程序自然应该得到满分，而那些貌似正确的程序则会在某些
特殊数据上出错。
在本题中，你在比赛中的角色反转啦！作为一名久经百战的程序员，你将帮
助 Happy Programmer Contest 的命题委员会设计这次比赛的测试数据。本次比
赛命题委员会选择了两个图论问题，分为 8 个子任务。委员会写了一些貌似可以
解决这些子任务的代码。在给任务设计数据的时候，命题委员会期望其中的一些
源程序能够得到满分，而另外的一些则只能得到 0 分或者少许的部分分。现在你
将会获得这些源程序（C,C++以及 Pascal 版本）。对于每个子任务，你需要去产
生一组数据 X 使得它能将该任务给定的 2 种源程序 A 和 B 区分开来。更具体地
说，生成的数据必须满足如下两个条件：
1. 输入 X 对于源程序 A 一定不会出现超出时间限制（TLE）的问题。
2. 输入 X 一定会导致源程序 B 产生超出时间限制的问题。
此外，命题委员喜欢较小规模的测试数据，希望测试数据最好能够包含不超
过 T 个整数。
（译注：本题中只关心源程序 A 和 B 是否超时，不关心是否结果正确）
命题委员会选择了单源最短路（SSSP）以及一个被称之为神秘问题（Mystery）
的两个图论问题来作为比赛的题目。我们将命题委员会完成的伪代码列在了附录
中，而具体的 C++和 Pascal 源程序被我们放在了下发的文件当中。
【数据描述】
参见下表。表中每一行描述了一个子任务。其中前六个子任务与单源最短路
相关，子任务 7,8 与神秘问题相关。每个任务所占分数见下表。
测试点
分数 S T 的限制 问题 源程序 A 源程序 B
编号
1 3 107 SSSP ModifiedDijkstra FloydWarshall
2 7 2222 SSSP FloydWarshall OptimizedBellmanFord
3 8 105 SSSP OptimizedBellmanFord FloydWarshall
4 17 157 SSSP FloydWarshall ModifiedDijkstra
5 10 1016 SSSP ModifiedDijkstra OptimizedBellmanFord
6 19 143 SSSP OptimizedBellmanFord ModifiedDijkstra
7 11 3004 Mystery Gamble1 RecursiveBactracking
8 25 3004 Mystery RecursiveBactracking Gamble2
对于每个子任务，你的程序给出的输入 X 需要能够将源程序 A 和 B 区分开
来，这有这样你才能够得到相应的分数。具体说来，你的分数将由输入 X 中数的
第 6 页 共 11 页
2013 亚太地区信息学奥林匹克竞赛
出题人
个数决定。假设 X 中包含了 F 个整数，子任务的满分为 S，T 是该任务的目标大
小，则该测试点的分数将由下式给出：
0.5 + S * min{T / F, 1}
也就是说，如果你的测试数据 X 中含有不超过 T 个整数，则你将得到该任
务的全部得分。
【评分标准】
你需要将你的 8 个测试数据命名为 tasksauthor.outX.1，其中的 X 是
子任务的编号。在提交前，你需要将你的测试数据使用 gzip 进行压缩。在 Unix
系统下，可以使用如下命令压缩文件：
tar -cvzf tasksauthor.tgz tasksauthor.out*.1
而在 Windows 系统中，可以使用 7-Zip 或是 Winzip 来进行压缩。最后将打
包后的文件 tasksauthor.tgz 提交至评测服务器中。
评测服务器将会把你提交的文件解压缩。对于每个子任务 X，评测系统将根
据如下步骤来确定你将会得到多少分：
1. 如果 tasksauthor.outX.1不存在，则不得分；
2. 若 tasksauthor.outX.1不满足输入格式要求，则不得分；
3. 对源程序 A 运行输入 tasksauthor.outX.1，若发生超时现象，则不
得分；
4. 对源程序 B 运行输入 tasksauthor.outX.1，若发生超时现象，则按
照下述公式给出该测试点的分数：
0.5 + S * min{T / F, 1}
题目提供的所有源代码均会维护一个计数器来统计程序的操作次数。在源程
序的运行过程中，当该计数器超过了 1,000,000 次时，那么我们认为程序运行超
时。
【问题描述 1：单源最短路(SSSP)】
给定一个带权有向图 G，以及 G 中的两个节点 s 与 t，令 p(s, t) 为 G 中从
s 至 t 的最短路长度。如果 s 与 t 不连通，则认为 p(s, t)=1,000,000,000。在本题
中，输入为图 G 以及 Q 个询问(s1, t1), (s2, t2 ), …, (sQ, tQ)。输出则是对这 Q 个询问
的相应输出 p(s1, t1), p(s2, t2 ), …, p(sQ, tQ)。
【问题 1 输入输出格式】
输入数据包含 2 部分，其中第一部分使用邻接表来描述带权有向图 G。第二
部分则描述对 G 的最短路径的查询。
数据第一部分的第一行包含一个整数 V，表示 G 中点的个数，所有点的编号
为 0, 1, …, V – 1。
接下来 V 行，每行描述一个点的所有边。行中的第一个整数 ni 描述了节点
i 的出边数量，接下来有 ni 个整数对 (j, w) 表示有一条从 i 到 j ，边权为 w
的边。
数据第二部分的第一行包含一个整数 Q，表示询问的组数。
第 7 页 共 11 页
2013 亚太地区信息学奥林匹克竞赛
出题人
接下来 Q 行，第 k 行包含两个整数 sk, tk，为该询问对应的起点与终点位置。
同一行中任意两个相邻的整数均需要至少一个空格将他们分开。除此之外，
数据还需满足如下条件：
1. 0 < V ≤ 300；
2. ni 是一个非负整数；
3. 0 ≤ j < V；
4. |w| < 106；
5. 0 ≤ ∑V 1i=0 ≤ 5000；
6. 0 < Q ≤ 10；
7. 0 ≤ sk < V, 0 ≤ tk < V；
8. 所有询问中的起点 sk 都不能达到任何一个负权圈。
程序将会输出 Q 行，每行一个整数，表示对应的 p(sk, tk)。而在输出的最后，
所有提供的程序都会给出计数器对此输入的数值。
【问题 1 样例输入】1
3
2 1 4 2 1
0
1 1 2
2
0 1
1 0
【问题 1 样例输出】2
3
1000000000
The value of counter is: 5
图：问题 1 样例输入中的有向带权图
1 输入包含 15 个整数，因此 F = 15。
2 将给定的样例输入使用 ModifiedDijkstra.cpp/pas 运行时，counter 的值为 5。
第 8 页 共 11 页
2013 亚太地区信息学奥林匹克竞赛
出题人
【问题描述 2：神秘问题】
给定一个包含 V 个节点 E 条边的无向图 G，要求将所有的节点进行编号（编
号范围为[0 .. (X-1)]），使得所有直接相连的节点均有不同的编号。找出符合题
意的最小的 X。
【问题 2 输入输出格式】
输入数据的第一行包含两个整数 V 和 E。
接下来 E 行，每行两个整数 a, b，表示 a 与 b 在 G 中直接相连。此外，输入
数据应满足如下限制条件：
1. 70 < V < 1000；
2. 1500 < E < 106；
3. 对于所有的边 (a, b)，有 a ≠ b, 0 ≤ a < V, 0 ≤ b < V，不会重复描述一条
边。
程序将在第一行输出 X，即最小的编号范围，接下来在第二行中给出 V 个整
数，依次描述节点 0 至 V – 1 的编号。在输出的最后，所有提供的程序都会给出
计数器对此输入的数值。
【问题 2 样例输入】3
4 5
0 1
0 2
0 3
1 2
2 3
【问题 2 样例输出】4
3
0 1 2 1
The value of counter is: 18
图：左图为问题 2 样例输入中的无向图，右图为 X=3 的一种标号
3 输入包含 12 个整数，因此 F=12。这个例子只是一个示例，其中 V 和 E 的值都不满足数据的限制（太
小）。
4 将给定的样例输入使用 RecursiveBacktracking.cpp/pas 运行时，counter 的值为 5。
第 9 页 共 11 页
2013 亚太地区信息学奥林匹克竞赛
出题人
【附录：伪代码】
接下来是我们提供的所有程序的伪代码；变量 counter 近似描述出了程
序的运行时间。评测服务器将会使用这些伪代码的 c++ 版本来进行评测。
【FloydWarshall.cpp/pas】
// pre-condition: the graph is stored in an adjacency matrix M
counter = 0
for k = 0 to V-1
for i = 0 to V-1
for j = 0 to V-1
increase counter by 1;
M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
for each query p(s,t)
output M[s][t];
【OptimizedBellmanFord.cpp/pas】
// pre-condition: the graph is stored in an adjacency list L
counter = 0
for each query p(s,t);
dist[s] = 0; // s is the source vertex
loop V-1 times
change = false;
for each edge (u,v) in L
increase counter by 1;
if dist[u] + weight(u,v) < dist[v]
dist[v] = dist[u] + weight(u,v);
change = true;
if change is false // this is the ’optimized’ Bellman Ford
break from the outermost loop;
output dist[t];
【ModifiedDijkstra.cpp/pas】
// pre-condition: the graph is stored in an adjacency list L
counter = 0;
for each query p(s,t)
dist[s] = 0;
pq.push(pair(0, s)); // pq is a priority queue
while pq is not empty
increase counter by 1;
(d, u) = the top element of pq;
remove the top element from pq;
第 10 页 共 11 页
2013 亚太地区信息学奥林匹克竞赛
出题人
if (d == dist[u])
for each edge (u,v) in L
if (dist[u] + weight(u,v) ) < dist[v]
dist[v] = dist[u] + weight(u,v);
insert pair (dist[v], v) into the pq;
output dist[t];
【Gamble1.cpp/pas】
Sets X = V and labels vertex i in [0..V-1] with i;
Sets counter = 0; // will never get TLE
【Gamble2.cpp/pas】
Sets X = V and labels vertex i in [0..V-1] with i;
Sets counter = 1000001; // force this to get TLE
【RecursiveBacktracking.cpp/pas】
This algorithm tries X from 2 to V one by one
and stops at the first valid X.
For each X, the backtracking routine label vertex 0 with 0,
then for each vertex u that has been assigned a label,
the backtracking routine tries to assign
the smallest possible label up to label X-1 to its neighbor v,
and backtracks if necessary.
// Please check RecursiveBacktracking.cpp/pas to see
// the exact lines where the iteration counter is increased by 1
第 11 页 共 11 页本资料来自于资源最齐全的２１世纪教育网www.21cnjy.com
2013亚太地区信息学奥林匹克竞赛
APIO 2013
竞赛时间：2013年5月11日9:00-14:00
题目名称 机器人 道路费用 出题人
英文名称 ROBOTS TOLL TASKSAUTHOR
输入 标准输入
输出 标准输出
每个测试点时限 1.5 秒 2.5 秒 /
内存限制 128 MB 128MB /
试题总分 100 100 100
测试点数目 20 20 8
每个测试点分值 5 5 见题面
编译器版本及编译选项见考试注意事项。
机器人
【问题描述】
VRI（Voltron机器人学会）的工程师建造了n个机器人。任意两个兼容的机器人站在同一个格子时可以合并为一个复合机器人。
我们把机器人用1至n编号（n ≤ 9）。如果两个机器人的编号是连续的，那么它们是兼容的，可以合并成一个复合机器人。最初这n个机器人各自都只有唯一的编号。而一个由两个或以上的机器人合并构成的复合机器人拥有两个编号，分别是构成它的所有机器人中最小和最大的编号。
例如，2号机器人只可以与1号或3号机器人合并。若2号机器人与3号机器人合并，可构成编号为2-3的复合机器人。如果编号为2-3的复合机器人与编号为4-6的复合机器人合并，可构成编号为2-6的复合机器人。当所有机器人合并以后则构成1-n复合机器人。
工程师把这n个机器人放在了一个封闭的房间中，房间四周均是墙。该房间被划分成w × h个方格。有些方格有障碍物，机器人不可经过或停留；其余方格允许多个机器人停留，同时允许机器人经过。任何时候一个机器人只占用一个方格。初始时刻，所有机器人均在不同的方格中。
这些原始的机器人不会自发地移动。它们只有被工程师沿x轴或y轴推动后，才会沿推动的方向不断向前直线移动，直至碰到障碍物或墙停止移动。停止移动后，它会扫描当前的格子是否存在可以与它合并的机器人，如果有，则合并并继续检查，直至不能再合并为止。工程师只能沿水平向左、水平向右、竖直向上、竖直向下四个方向推动机器人，并且，在机器人尚未停止移动时，不允许推动其它机器人，因此任何时刻，房间中都只能有一个机器人移动。
为了帮助机器人转向，工程师在一些格子中放置了转向器。具体地说，转向器分为顺时针转向器（右转器）和逆时针转向器（左转器），顺时针转向器可以使到达该格子的机器人沿顺时针方向转向90°；逆时针转向器可以使到达该格子的机器人沿逆时针方向转向90°。
现在，我们将告诉你初始时刻房间内的信息。请你计算工程师最少共计需要推动机器人多少次，才能把所有的n个机器人全部合并（如果可能的话）。
【输入格式】
你的程序必须从标准输入读入。输入的第1行包含3个整数n、w和h，用空格隔开。
输入文件中接下来的h行描述初始时刻房间内的信息，每行包含w个字符。这w × h个字符中每一个表示房间中的一个格子，意义如下：
‘1’至‘9’：表示该方格中有一个机器人，编号为这个数字；
‘x’：表示该方格有障碍物；
‘A’：表示该方格中有一个逆时针转向器；
‘C’：表示该方格中有一个顺时针转向器；
‘.’：表示该方格为空地。
【输出格式】
你的程序必须输出到标准输出。输出仅一个整数，表示最少需要推动的次数。若不能使所有机器人全部合并，输出-1。
【样例输入】
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
【样例输出】
5
【样例说明】
第一步：向右推动3号机器人，当它碰到转向器后会向上继续移动，直至碰到墙壁停止移动。
第二步：向上推动4号机器人，当它碰到墙壁后停止移动，与3号机器人合并，构成3-4号机器人
第三步：向上推动2号机器人，当它碰到转向器后会向左移动，由于左侧为墙壁，故停留在原地。
第四步：向右推动2号机器人，由于它在一个转向器上，故它会向上移动，直至碰到墙壁停止移动，与1号机器人合并，构成1-2号机器人。
第五步：向左推动3-4号机器人，当它碰到墙壁后停止移动，与1-2号机器人合并，构成1-4号机器人。
【数据规模与约定】
我们将使用以下4类输入测例测试你的程序。
1. （10分）测例满足n = 2，w ≤ 10且h ≤ 10，没有任何转向器。
2. （20分）测例满足n = 2，w ≤ 10且h ≤ 10。
3. （30分）测例满足n ≤ 9，w ≤ 300且h ≤ 300。
4. （40分）测例满足n ≤ 9，w ≤ 500且h ≤ 500。
道路费用
【问题描述】
幸福国度可以用N个城镇（用1到N编号）构成的集合来描述，这些城镇最开始由M条双向道路（用1到M编号）连接。城镇1是中央城镇。保证一个人从城镇1出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是收费道路，道路i的使用者必须向道路的主人支付ci分钱的费用。已知所有的这些ci是互不相等的。最近有K条新道路建成，这些道路都属于亿万富豪Mr. Greedy。Mr. Greedy可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣布这些费用。
两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这些道路游行并前往中央城镇。共计pj个参与者将从城镇j出发前往中央城镇。这些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就是Mr. Greedy。同样根据这个习俗，Mr. Greedy选出的这个道路集合必须使所有选出道路的费用之和最小，并且仍要保证任何人可以从城镇j前往城镇1（因此，这些选出的道路来自将费用作为相应边边权的“最小生成树”）。如果有多个这样的道路集合，Mr. Greedy可以选其中的任何一个，只要满足费用和是最小的。
Mr. Greedy很明确地知道，他从K条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果p个人经过道路i，道路i产生的收入为ci p的积。注意Mr. Greedy只能从新道路收取费用，因为原来的道路都不属于他。
Mr. Greedy有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路（将在嘉年华的前一天公布），使得他在K条新道路的收入最大。注意Mr. Greedy仍然需要遵循选出花费之和最小的道路集合的习俗。
你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序来确定Mr. Greedy可以通过他的阴谋获取多少收入。
【输入格式】
你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数N，M和K。接下来的M行描述最开始的M条道路。这M行中的第i行包含由空格隔开的整数ai，bi和ci，表示有一条在ai和bi之间，费用为ci的双向道路。接下来的K行描述新建的K条道路。这K行中的第i行包含由空格隔开的整数xi和yi，表示有一条连接城镇xi和yi新道路。最后一行包含N个由空格隔开的整数，其中的第j个为pj，表示从城镇j前往城镇1的人数。
输入也满足以下约束条件。
1 ≤ N ≤ 100000；
1 ≤ K ≤ 20；
1 ≤ M ≤ 300000；
对每个i和j，1 ≤ ci, pj ≤ 106；
如果i ≠ i'，则ci ≠ ci'；
在任意两个城市之间，最多只有一条道路（包括新建的道路）。
【输出格式】
你的程序必须输出恰好一个整数到标准输出，表示能获得的最大的收入。
【样例输入】
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
【样例输出】
400
【样例说明】
在样例中，Mr. Greedy应该将新道路(1,3)的费用设置为5分钱。在这个费用下，他可以选择道路(3,5)，(1,2)，(2,4)和(1,3)来最小化总费用，这个费用为14。从城镇3出发的30个人和从城镇5出发的50个人将经过新道路前往城镇1，因此他可以获得为(30+50)×5=400分钱的最好收入。
如果我们这样做，将新道路(1,3)的费用设置为10分钱。根据传统的限制，Mr. Greedy必须选择(3,5)，(1,2)，(2,4)和(2,3)，因为这是唯一费用最小的集合。因此，在嘉年华的过程中道路(1,3)将没有任何收入。
【数据规模与约定】
我们将使用以下5类测例测试你的程序。
1. （国际16分，国内15分）N ≤ 10，M ≤ 20且K = 1；
2. （国际18分，国内20分）N ≤ 30，M ≤ 50且K ≤ 10；
3. （国际22分，国内20分）N ≤ 1,000，M ≤ 5,000且K ≤ 10；
4. （国际22分，国内20分）N ≤ 100,000，M ≤ 300,000且K ≤ 15；
5. （国际22分，国内25分）N ≤ 100,000，M ≤ 300,000且K ≤ 20。
出题人
【问题描述】
当今世界上各类程序设计竞赛层出不穷。而设计一场好比赛绝非易事，比如给题目设计测试数据就是一项挑战。一组好的测试数据需要对不同的程序有区分度：满足所有要求的程序自然应该得到满分，而那些貌似正确的程序则会在某些特殊数据上出错。
在本题中，你在比赛中的角色反转啦！作为一名久经百战的程序员，你将帮助 Happy Programmer Contest 的命题委员会设计这次比赛的测试数据。本次比赛命题委员会选择了两个图论问题，分为8个子任务。委员会写了一些貌似可以解决这些子任务的代码。在给任务设计数据的时候，命题委员会期望其中的一些源程序能够得到满分，而另外的一些则只能得到0分或者少许的部分分。现在你将会获得这些源程序（C,C++以及Pascal版本）。对于每个子任务，你需要去产生一组数据X使得它能将该任务给定的2种源程序A和B区分开来。更具体地说，生成的数据必须满足如下两个条件：
1. 输入X对于源程序A一定不会出现超出时间限制（TLE）的问题。
2. 输入X一定会导致源程序B产生超出时间限制的问题。
此外，命题委员喜欢较小规模的测试数据，希望测试数据最好能够包含不超过T个整数。
（译注：本题中只关心源程序A和B是否超时，不关心是否结果正确）
命题委员会选择了单源最短路（SSSP）以及一个被称之为神秘问题（Mystery）的两个图论问题来作为比赛的题目。我们将命题委员会完成的伪代码列在了附录中，而具体的C++和Pascal源程序被我们放在了下发的文件当中。
【数据描述】
参见下表。表中每一行描述了一个子任务。其中前六个子任务与单源最短路相关，子任务7,8与神秘问题相关。每个任务所占分数见下表。
测试点编号 分数S T的限制 问题 源程序A 源程序B
1 3 107 SSSP ModifiedDijkstra FloydWarshall
2 7 2222 SSSP FloydWarshall OptimizedBellmanFord
3 8 105 SSSP OptimizedBellmanFord FloydWarshall
4 17 157 SSSP FloydWarshall ModifiedDijkstra
5 10 1016 SSSP ModifiedDijkstra OptimizedBellmanFord
6 19 143 SSSP OptimizedBellmanFord ModifiedDijkstra
7 11 3004 Mystery Gamble1 RecursiveBactracking
8 25 3004 Mystery RecursiveBactracking Gamble2
对于每个子任务，你的程序给出的输入X需要能够将源程序A和B区分开来，这有这样你才能够得到相应的分数。具体说来，你的分数将由输入X中数的个数决定。假设X中包含了F个整数，子任务的满分为S，T是该任务的目标大小，则该测试点的分数将由下式给出：
0.5 + S * min{T / F, 1}
也就是说，如果你的测试数据X中含有不超过 T 个整数，则你将得到该任务的全部得分。
【评分标准】
你需要将你的8个测试数据命名为tasksauthor.outX.1，其中的 X 是子任务的编号。在提交前，你需要将你的测试数据使用gzip进行压缩。在Unix系统下，可以使用如下命令压缩文件：
tar -cvzf tasksauthor.tgz tasksauthor.out*.1
而在Windows系统中，可以使用7-Zip或是Winzip来进行压缩。最后将打包后的文件 tasksauthor.tgz 提交至评测服务器中。
评测服务器将会把你提交的文件解压缩。对于每个子任务X，评测系统将根据如下步骤来确定你将会得到多少分：
1. 如果tasksauthor.outX.1不存在，则不得分；
2. 若tasksauthor.outX.1不满足输入格式要求，则不得分；
3. 对源程序A运行输入tasksauthor.outX.1，若发生超时现象，则不得分；
4. 对源程序B运行输入tasksauthor.outX.1，若发生超时现象，则按照下述公式给出该测试点的分数：
0.5 + S * min{T / F, 1}
题目提供的所有源代码均会维护一个计数器来统计程序的操作次数。在源程序的运行过程中，当该计数器超过了1,000,000次时，那么我们认为程序运行超时。
【问题描述1：单源最短路(SSSP)】
给定一个带权有向图G，以及G中的两个节点s与t，令 p(s, t) 为G中从s至t的最短路长度。如果s与t不连通，则认为p(s, t)=1,000,000,000。在本题中，输入为图G以及Q个询问(s1, t1), (s2, t2 ), …, (sQ, tQ)。输出则是对这Q个询问的相应输出p(s1, t1), p(s2, t2 ), …, p(sQ, tQ)。
【问题1输入输出格式】
输入数据包含2部分，其中第一部分使用邻接表来描述带权有向图G。第二部分则描述对G的最短路径的查询。
数据第一部分的第一行包含一个整数V，表示G中点的个数，所有点的编号为0, 1, …, V – 1。
接下来V行，每行描述一个点的所有边。行中的第一个整数 ni 描述了节点 i 的出边数量，接下来有 ni 个整数对 (j, w) 表示有一条从 i 到 j ，边权为 w的边。
数据第二部分的第一行包含一个整数Q，表示询问的组数。
接下来Q行，第k行包含两个整数 sk, tk，为该询问对应的起点与终点位置。
同一行中任意两个相邻的整数均需要至少一个空格将他们分开。除此之外，数据还需满足如下条件：
1. 0 < V ≤ 300；
2. ni 是一个非负整数；
3. 0 ≤ j < V；
4. |w| < 106；
5. 0 ≤ ≤ 5000；
6. 0 < Q ≤ 10；
7. 0 ≤ sk < V, 0 ≤ tk < V；
8. 所有询问中的起点sk 都不能达到任何一个负权圈。
程序将会输出Q行，每行一个整数，表示对应的p(sk, tk)。而在输出的最后，所有提供的程序都会给出计数器对此输入的数值。
【问题1样例输入】 [1]
3
2 1 4 2 1
0
1 1 2
2
0 1
1 0
【问题1样例输出】 [2]
3
1000000000
The value of counter is: 5
图：问题1样例输入中的有向带权图
【问题描述2：神秘问题】
给定一个包含V个节点E条边的无向图G，要求将所有的节点进行编号（编号范围为[0 .. (X-1)]），使得所有直接相连的节点均有不同的编号。找出符合题意的最小的 X。
【问题2输入输出格式】
输入数据的第一行包含两个整数V和E。
接下来E行，每行两个整数a, b，表示a与b在G中直接相连。此外，输入数据应满足如下限制条件：
1. 70 < V < 1000；
2. 1500 < E < 106；
3. 对于所有的边 (a, b)，有 a ≠ b, 0 ≤ a < V, 0 ≤ b < V，不会重复描述一条边。
程序将在第一行输出X，即最小的编号范围，接下来在第二行中给出V个整数，依次描述节点0至V – 1的编号。在输出的最后，所有提供的程序都会给出计数器对此输入的数值。
【问题2样例输入】 [3]
4 5
0 1
0 2
0 3
1 2
2 3
【问题2样例输出】 [4]
3
0 1 2 1
The value of counter is: 18
图：左图为问题2样例输入中的无向图，右图为X=3的一种标号
【附录：伪代码】
接下来是我们提供的所有程序的伪代码；变量 counter 近似描述出了程序的运行时间。评测服务器将会使用这些伪代码的 c++ 版本来进行评测。
【FloydWarshall.cpp/pas】
// pre-condition: the graph is stored in an adjacency matrix M
counter = 0
for k = 0 to V-1
for i = 0 to V-1
for j = 0 to V-1
increase counter by 1;
M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
for each query p(s,t)
output M[s][t];
【OptimizedBellmanFord.cpp/pas】
// pre-condition: the graph is stored in an adjacency list L
counter = 0
for each query p(s,t);
dist[s] = 0; // s is the source vertex
loop V-1 times
change = false;
for each edge (u,v) in L
increase counter by 1;
if dist[u] + weight(u,v) < dist[v]
dist[v] = dist[u] + weight(u,v);
change = true;
if change is false // this is the ’optimized’ Bellman Ford
break from the outermost loop;
output dist[t];
【ModifiedDijkstra.cpp/pas】
// pre-condition: the graph is stored in an adjacency list L
counter = 0;
for each query p(s,t)
dist[s] = 0;
pq.push(pair(0, s)); // pq is a priority queue
while pq is not empty
increase counter by 1;
(d, u) = the top element of pq;
remove the top element from pq;
if (d == dist[u])
for each edge (u,v) in L
if (dist[u] + weight(u,v) ) < dist[v]
dist[v] = dist[u] + weight(u,v);
insert pair (dist[v], v) into the pq;
output dist[t];
【Gamble1.cpp/pas】
Sets X = V and labels vertex i in [0..V-1] with i;
Sets counter = 0; // will never get TLE
【Gamble2.cpp/pas】
Sets X = V and labels vertex i in [0..V-1] with i;
Sets counter = 1000001; // force this to get TLE
【RecursiveBacktracking.cpp/pas】
This algorithm tries X from 2 to V one by one
and stops at the first valid X.
For each X, the backtracking routine label vertex 0 with 0,
then for each vertex u that has been assigned a label,
the backtracking routine tries to assign
the smallest possible label up to label X-1 to its neighbor v,
and backtracks if necessary.
// Please check RecursiveBacktracking.cpp/pas to see
// the exact lines where the iteration counter is increased by 1
21世纪教育网 -- 中国最大型、最专业的中小学教育资源门户网站。 版权所有@21世纪教育网
^1 输入包含15个整数，因此F = 15。
^2 将给定的样例输入使用ModifiedDijkstra.cpp/pas运行时，counter的值为5。
^3 输入包含12个整数，因此F=12。这个例子只是一个示例，其中V和 E的值都不满足数据的限制（太小）。
^4 将给定的样例输入使用RecursiveBacktracking.cpp/pas运行时，counter的值为5。

展开更多......

收起↑