分数: 800 点
问题陈述
有一个连通无向图 N 顶点和 M 边缘。 顶点已编号 1 to N,并且边缘已编号 1 to M。 此外,每个顶点和边都有指定的权重。 顶点 i 的重量为 X_i;边缘 i 的重量为 Y_i 并连接顶点 A_i 和 B_i.
我们想要删除零个或多个边缘,以便满足以下条件:
- 对于每条未移除的边,包含该边的连通分量中的顶点权重之和大于或等于该边的权重。
找到需要删除的最少边数。
约束
- 1 \leq N \leq 10^5
- N-1 \leq M \leq 10^5
- 1 \leq X_i \leq 10^9
- 1 \leq A_i < B_i \leq N
- 1 \leq Y_i \leq 10^9
- (A_i,B_i) \neq (A_j,B_j) (i \neq j)
- 给定的图形已连接。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M X_1 X_2 ... X_N A_1 B_1 Y_1 A_2 B_2 Y_2 : A_M B_M Y_M
输出
找到需要删除的最少边数。
示例输入 1
4 4 2 3 5 7 1 2 7 1 3 9 2 3 12 3 4 18
示例输出 1
2
假设我们删除了 Edge 3 和 4。 在这种情况下,包含 Edge 的连接组件 1 包含顶点 1, 2 和 3,这些顶点的权重之和为 2+3+5=10。 Edge 的重量 1 is 7,因此 Edge 满足条件 1。 同理,可以看出Edge也满足条件 2。 这样,去掉两条边就可以得到满足条件的图。
删除一条或更少的边不能满足条件,所以答案是 2.
示例输入 2
6 10 4 4 1 1 1 7 3 5 19 2 5 20 4 5 8 1 6 16 2 3 9 3 6 16 3 4 1 2 6 20 2 4 19 1 2 9
示例输出 2
4
示例输入 3
10 9 81 16 73 7 2 61 86 38 90 28 6 8 725 3 10 12 1 4 558 4 9 615 5 6 942 8 9 918 2 7 720 4 7 292 7 10 414
示例输出 3
8