A4824 | 可恶の施工
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
JW 家附近正在施工。
JW 家附近可以看作是由 $N$ 个区域和 $M$ 条双向道路连接的。现在由于施工，一些道路被封锁了。
JW 正准备去上学，突然有几个工人找到他问：我们需要让道路的总长度不超过 $p$，同时使所有区域保持连通，最少要拆除几条道路？原来，是工人们都想不出来这个问题，才找到了 JW。
你或许认为，这是 JW 的事，不关你的事。你是对的，但是到了学校之后 JW 一直在你面前叨叨，你为了保护自己的耳朵，不得不去解决这个无聊的问题。
JW 家附近可以看作是由 $N$ 个区域和 $M$ 条双向道路连接的。现在由于施工，一些道路被封锁了。
JW 正准备去上学，突然有几个工人找到他问：我们需要让道路的总长度不超过 $p$，同时使所有区域保持连通，最少要拆除几条道路？原来，是工人们都想不出来这个问题，才找到了 JW。
你或许认为，这是 JW 的事，不关你的事。你是对的，但是到了学校之后 JW 一直在你面前叨叨，你为了保护自己的耳朵，不得不去解决这个无聊的问题。
输入格式
输入共若干行：
第一行共 $1$ 个整数 $T$，表示问题组数；
每组数据的第一行共 $3$ 个整数 $N,M$ 和 $p$，分别表示区域的数量、道路的数量和工人的要求。
接下来 $M$ 行，每行 $3$ 个整数 $u,v,w$，分别表示道路连接的两个区域和道路的长度。
第一行共 $1$ 个整数 $T$，表示问题组数；
每组数据的第一行共 $3$ 个整数 $N,M$ 和 $p$，分别表示区域的数量、道路的数量和工人的要求。
接下来 $M$ 行，每行 $3$ 个整数 $u,v,w$，分别表示道路连接的两个区域和道路的长度。
输出格式
输出共 $T$ 行：
对于每组输入，输出最少要拆除的道路数量。如果无论如何拆除都无法满足要求，则输出
对于每组输入，输出最少要拆除的道路数量。如果无论如何拆除都无法满足要求，则输出
NO。输入输出样例
输入 #1
3 5 7 13 1 5 2 2 5 3 5 3 3 4 5 2 3 4 4 2 4 5 2 3 4 3 4 6 1 2 1 1 3 5 1 2 3 1 2 1 6 8 4 1 6 1 4 6 1 2 5 1 3 5 1 2 3 1 3 4 1 1 3 1 1 4 1
输出 #1
3 2 NO
【数据范围】
对于所有数据，保证：
$1 \leq T \leq 5$，$1 \leq u,v \leq N \leq 10^5$，$1\le M\le10^5$，$1 \leq p \leq 10^{18}$，$1 \leq w \leq 10^9$
| 测试点 | $N,M \leq$ | 特殊性质 |
|---|---|---|
| 1,2 | $10$ | 无 |
| 3,4 | $100$ | A |
| 5,6 | $100$ | B |
| 7,8,9 | $10^5$ | A |
| 10~20 | $10^5$ | 无 |
特殊性质 A：所有的 $w$ 均相等。
特殊性质 B：$N-M=1$。
本题测试点等分。
【样例解释】
样例组 #1：
道路总长度为 $23$。删除 $3$ 条道路后如下：
此时道路总长度为 $11$，$11\leq 13$。
可以证明，没有拆除道路更少的方法。
样例组 #2：道路总长为 $10$。拆除一条 $u=1,v=2,w=1$ 和一条 $u=1,v=1,w=3$ 的道路后总长为 $6$。注意，如果拆除 $u=1,v=3,w=5$ 的道路无法连通 $3$ 区域，不可取。
样例组 #3：可以证明，无论如何都无法达到要求。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？