#PQJ1689x8735. QOJ 1689_8735
QOJ 1689_8735
IOI2011 中国国家队选拔赛 第一试 道路监控 道路监控 【问题描述】 道路安全部门最近计划部署从A 市到B 市的道路监控系统,以提高该部门 对于紧急事件的应对能力。A 市到B 市的道路网可以描述为一个无向图G=(V, E), 其中V 表示道路网中的节点集合, E 表示连接节点的双向道路集合。所有的节点 由1~n 进行编号,其中n 为节点个数。A 市所处的节点为s, B 市所处的节点为t。 该部门计划在其中一些道路中安装监控设备,以降低整个道路网的响应难度。 当紧急事件发生时,部门需要派遣一些人力到一些道路中进行执勤,以使得任何 一条从节点s 到达节点t 的路径都经过至少一条监控道路(安装了监控设备或者 有人执勤)。因此响应难度定义为需要派遣人力的最少道路数,以使得任何一条 从s 到t 的路径都经过至少一条监控道路。 由于自然环境不同,在不同的道路安装监控设备的代价也可能不同。具体而 言,对于一条边e,其安装设备的代价为W(e)。由于经费有限,他们希望找到一 个方案,使得该道路网的响应难度不超过k。请你帮助他们寻找一个尽可能经济 的部署方案。 【输入格式】 这是一道提交答案的试题,在你的目录下有10 个输入文件road*.in。 输入文件的第一行为三个整数n,m 和k,分别表示道路网中的节点数、道 路数以及响应难度的上限值。 输入文件第二行包含两个整数s 和t,表示A 市与B 市的节点编号。 接下来m 行,每行三个正整数ai,bi,wi,表示一条连接节点ai 和节点bi 的道路,其安装监控设备的费用为wi。 【输出格式】 对于每一个输入文件,在目录下给出对应的输出文件road*.out。 输出文件第一行包含一个值s,表示选手提供的方案中将在s 条道路上安装 监控设备。接下来s 行每行包含一个整数pi,表示在输入文件中的第pi 条道路上 安装监控设备(边从1 开始编号)。 【样例输入】 3 3 1 1 3 1 2 1 2 3 10 1 3 5 第6 页 共7 页 IOI2011 中国国家队选拔赛 第一试 道路监控 【样例输出】 1 1 【评分标准】 对于每个测试点,如果你没有输出或者输出不合法则得0 分。 对于每个测试点,我们设有五个评分参数m1、m2、m3、m4 和m5。假设选手 的方案中费用为c, 若c < m1,得12 分; 若c = m1,得10 分; 若m1 < c ≤ m2,得8 分; 若m2 < c ≤ m3,得5 分; 若m3 < c ≤ m4,得3 分; 若c < m5,得1 分; 否则,得0 分。 【如何测试你的输出】 在你的目录下有一个名为checker 的程序可以用来检查你的输出,你可以在 终端中使用以下命令来检查你的输出: ./checker N 其中N 为测试点的编号,例如,要测试第3 个测试点可以使用 ./checker 3 该程序会检测你的输出是否合法。如果方案合法,程序还会给出该方案的部 署费用总和。 第7 页 共7 页