luogu#P11322. [NOISG2020 Qualification] Firefighting

    ID: 35150 远端评测题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2020Special JudgeNOISG(新加坡)

[NOISG2020 Qualification] Firefighting

题目背景

在 Mouseopolis,这座鼠国的大都会,一场大火席卷了整座城市。为了防止类似灾难再次发生,鼠国的国王 Squeaky 决定在鼠国的城镇中建立消防站。

题目描述

鼠国由 NN 个城镇组成,编号为 11NN。城镇之间通过 N1N-1 条双向道路连接,每条道路连接两个城镇,并且道路的长度可能不同。城镇网络保证任何两个城镇之间都可以通过某些道路相连。

为了有效扑灭火灾,国王的顾问认为消防站到火灾发生地点的距离不得超过 KK 公里,否则火势将难以控制。然而,建设消防站的成本较高,国王希望尽可能减少消防站的数量。

任务是确定在鼠国的哪些城镇建设消防站,以使得需要建设的消防站数量最少。

输入格式

  • 第一行包含两个整数 NNKK,分别表示城镇的数量和消防站的最大服务距离。
  • 接下来的 N1N-1 行,每行包含三个整数 Ai,Bi,DiA_i, B_i, D_i,表示城镇 AiA_i 和城镇 BiB_i 之间有一条长度为 DiD_i 公里的双向道路。

输出格式

  • 第一行包含一个整数 FF,表示需要建设的最少消防站数量。
  • 第二行包含 FF 个整数,表示建设消防站的城镇编号。

可以按任意顺序输出。如果有多种可行方案,输出任意一种即可。

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,最少需要在城镇 1,8,3,61, 8, 3, 6 建立消防站,以保证每个城镇到最近的消防站的距离不超过 44 公里。

对于样例 #2,最少需要在城镇 5,6,2,35, 6, 2, 3 建立消防站。

对于样例 #3,必须在每个城镇建立消防站。

对于样例 #4,可以在城镇 441010 建立消防站,或者选择其他符合条件的方案。

【数据范围】

  • 1N3×1051 \leq N \leq 3 \times 10^5
  • 1K10151 \leq K \leq 10^{15}
  • 1Ai,BiN1 \leq A_i, B_i \leq N
  • 1Di1091 \leq D_i \leq 10^9
子任务编号 分值 限制条件
11 33 K20K \leq 20,且 Di30D_i \geq 30
22 55 N17,K17N \leq 17, K \leq 17,且 Di=1D_i = 1
33 99 N17,K106N \leq 17, K \leq 10^6,且 Di104D_i \leq 10^4
44 1919 K30K \leq 30,且 Di20D_i \geq 20
55 2626 N3×103N \leq 3 \times 10^3
66 3838 无额外限制