luogu#P10758. [CTSC2011] 道路监控

    ID: 14694 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2011WC/CTSC/集训队提交答案Special Judge

[CTSC2011] 道路监控

题目描述

道路安全部门最近计划部署从 A 市到 B 市的道路监控系统,以提高该部门对于紧急事件的应对能力。A 市到 B 市的道路网可以描述为一个无向图 G=(V,E)G=(V, E),其中 VV 表示道路网中的节点集合,EE 表示连接节点的双向道路集合。所有的节点由 1n1\sim n 进行编号,其中 nn 为节点个数。A 市所处的节点为 ss,B 市所处的节点为 tt

该部门计划在其中一些道路中安装监控设备,以降低整个道路网的响应难度。当紧急事件发生时,部门需要派遣一些人力到一些道路中进行执勤,以使得任何一条从节点 ss 到达节点 tt 的路径都经过至少一条监控道路(安装了监控设备或者有人执勤)。因此响应难度定义为需要派遣人力的最少道路数,以使得任何一条从 sstt 的路径都经过至少一条监控道路。

由于自然环境不同,在不同的道路安装监控设备的代价也可能不同。具体而言,对于一条边 ee,其安装设备的代价为 W(e)W(e)。由于经费有限,他们希望找到一个方案,使得该道路网的响应难度不超过 kk。请你帮助他们寻找一个尽可能经济的部署方案。

输入格式

这是一道提交答案的试题,在你的目录下有 1010 个输入文件 road*.in

输入文件的第一行为三个整数 nnmmkk,分别表示道路网中的节点数、道路数以及响应难度的上限值。

输入文件第二行包含两个整数 sstt,表示 AA 市与 BB 市的节点编号。

接下来 mm 行,每行三个正整数 aia_ibib_iwiw_i,表示一条连接节点 aia_i 和节点 bib_i 的道路,其安装监控设备的费用为 wiw_i

输出格式

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

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

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

提示

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

对于每个测试点,我们设有五个评分参数 m1m_1m2m_2m3m_3m4m_4m5m_5。假设选手的方案中费用为 cc

  • c<m1c<m_1,得 1212 分;(备注:赛场上实际为得 1010 分)
  • c=m1c=m_1,得 1010 分;
  • m1<cm2m_1<c\leq m_2,得 88 分;
  • m2<cm3m_2<c\leq m_3,得 55 分;
  • m3<cm4m_3<c\leq m_4,得 33 分;
  • c<m5c<m_5,得 11 分;
  • 否则,得 00 分。