#2746. 「CTSC2011」道路监控

题目类型:答案提交 评测方式:Special Judge
上传者: 匿名

题目描述

道路安全部门最近计划部署从 A 市到 B 市的道路监控系统,以提高该部门对于紧急事件的应对能力。A 市到 B 市的道路网可以描述为一个无向图 G=(V, E) ,其中 V 表示道路网中的节点集合, E 表示连接节点的双向道路集合。所有的节点由 1\sim 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 行,每行三个正整数 a_i, b_i, w_i ,表示一条连接节点 a_i 和节点 b_i 的道路,其安装监控设备的费用为 w_i

输出格式

对于每一个输入文件,在目录下给出对应的输出文件 road*.out

输出文件第一行包含一个值 s ,表示选手提供的方案中将在 s 条道路上安装监控设备。接下来 s 行每行包含一个整数 p_i ,表示在输入文件中的第 p_i 条道路上安装监控设备(边从 1 开始编号)。

样例

样例输入

3 3 1
1 3
1 2 1
2 3 10
1 3 5

样例输出

1
1

数据范围与提示

评分标准

对于每个测试点,如果你没有输出或者输出不合法则得 0 分。

对于每个测试点,我们设有五个评分参数 m_1, m_2, m_3, m_4 m_5 。假设选手的方案中费用为 c

  • c \lt m_1 ,得 12 分;
  • c = m_1 ,得 10 分;
  • m_1 \lt c \le m_2 ,得 8 分;
  • m_2 \lt c \le m_3 ,得 5 分;
  • m_3 \lt c \le m_4 ,得 3 分;
  • c \lt m_5 ,得 1 分;
  • 否则,得 0 分。

如何测试你的输出

在你的目录下有一个名为 checker 的程序可以用来检查你的输出,在此提供源文件。你可以在终端中编译后使用以下命令来检查你的输出:

./checker N

其中 N 为测试点的编号,例如,要测试第 3 个测试点可以使用

./checker 3

该程序会检测你的输出是否合法。如果方案合法,程序还会给出该方案的部署费用总和。

需要注意的是,你的输出应与输入一同放在 checker 所在目录下。

编辑器加载中 …