← 返回题目列表

AtCoder · nikkei2019_qual_e

E. 顶点和边上的权重

中文机器翻译题面 查看原题

分数: 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