分数: 266 分
问题陈述
高桥管理着一个地区的电网,该地区包括 N 城市。每个城市编号为 1 to N和城市 i 有所需电量(需求) S_i 需要正常运行。
有 M 该地区输电线路,每条双向连接两个城市。的 j第3条输电线路连接城市 U_j 和城市 V_j 并且传输容量为 W_j。每条输电线路可以向其连接的两个城市中的每一个提供与其输电容量相等的电力。
电量 T_i 可以供应给城市 i 定义为具有城市的所有输电线路的输电容量之和 i 作为端点。也就是说,如果城市输电线路的输电容量 i 作为端点是 W_{j_1}, W_{j_2}, \ldots, W_{j_k},那么 T_i = W_{j_1} + W_{j_2} + \cdots + W_{j_k}。如果没有与城市的输电线路 i 作为端点,那么 T_i = 0.
城市 i 被称为“缺电城市”,如果 T_i < S_i 成立。
求缺电城市的数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
- 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
- 至多有一条传输线连接同一对城市(即所有对 (U_j, V_j) 是不同的)
- 所有输入值均为整数
输入
N M S_1 S_2 \ldots S_N U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
- 第一行包含 N,城市数量,以及 M,传输线的数量,以空格分隔。
- 第二行包含各个城市的需求 S_1, S_2, \ldots, S_N,用空格分隔。
- 以下 M 线提供有关传输线的信息。
- 的 (2 + j)第行包含城市 U_j 和 V_j 由 j第传输线路,及传输容量 W_j,用空格分隔。
输出
一行输出缺电城市数量。
示例输入 1
4 3 10 3 5 8 1 2 4 2 3 6 3 4 2
示例输出 1
2
示例输入 2
3 3 5 5 5 1 2 3 1 3 3 2 3 3
示例输出 2
0
示例输入 3
6 5 10 20 15 8 30 5 1 2 7 2 3 10 3 4 5 4 5 3 1 6 6
示例输出 3
2
示例输入 4
10 8 100 50 200 30 80 60 150 40 90 10 1 2 25 2 3 30 3 4 50 4 5 20 5 6 35 6 7 40 7 8 60 9 10 5
示例输出 4
6
示例输入 5
1 0 1
示例输出 5
1