luogu#P11322. [NOISG2020 Qualification] Firefighting
[NOISG2020 Qualification] Firefighting
题目背景
在 Mouseopolis,这座鼠国的大都会,一场大火席卷了整座城市。为了防止类似灾难再次发生,鼠国的国王 Squeaky 决定在鼠国的城镇中建立消防站。
题目描述
鼠国由 个城镇组成,编号为 到 。城镇之间通过 条双向道路连接,每条道路连接两个城镇,并且道路的长度可能不同。城镇网络保证任何两个城镇之间都可以通过某些道路相连。
为了有效扑灭火灾,国王的顾问认为消防站到火灾发生地点的距离不得超过 公里,否则火势将难以控制。然而,建设消防站的成本较高,国王希望尽可能减少消防站的数量。
任务是确定在鼠国的哪些城镇建设消防站,以使得需要建设的消防站数量最少。
输入格式
- 第一行包含两个整数 和 ,分别表示城镇的数量和消防站的最大服务距离。
- 接下来的 行,每行包含三个整数 ,表示城镇 和城镇 之间有一条长度为 公里的双向道路。
输出格式
- 第一行包含一个整数 ,表示需要建设的最少消防站数量。
- 第二行包含 个整数,表示建设消防站的城镇编号。
可以按任意顺序输出。如果有多种可行方案,输出任意一种即可。
9 4
1 2 10
2 3 4
8 9 4
8 7 3
7 3 5
3 4 1
4 5 3
5 6 2
4
1 8 3 6
9 26
2 1 21
2 9 21
2 8 21
2 3 56
3 4 37
4 5 29
7 6 25
6 4 24
4
5 6 2 3
3 18
1 2 35
2 3 49
3
1 2 3
10 3
10 9 1
9 8 1
8 5 1
1 2 1
2 3 1
5 4 1
3 4 1
5 6 1
6 7 1
2
4 10
提示
【样例解释】
对于样例 #1,最少需要在城镇 建立消防站,以保证每个城镇到最近的消防站的距离不超过 公里。
对于样例 #2,最少需要在城镇 建立消防站。
对于样例 #3,必须在每个城镇建立消防站。
对于样例 #4,可以在城镇 和 建立消防站,或者选择其他符合条件的方案。
【数据范围】
子任务编号 | 分值 | 限制条件 |
---|---|---|
,且 | ||
,且 | ||
,且 | ||
,且 | ||
无额外限制 |