分数: 475 点
问题陈述
给你一个简单的无向图,包括 N 顶点和 M 边缘。 对于 i = 1, 2, \ldots, M, i第一条边连接顶点 u_i 和 v_i。 另外,对于 i = 1, 2, \ldots, N,顶点 i 被分配一个正整数 W_i,并且有 A_i 碎片放置在其上。
只要图形上有棋子,就重复以下操作:
- 首先,从图中选择并删除一个片段,然后让 x 是放置棋子的顶点。
- 选择一个(可能是空的)集合 S 相邻的顶点 x 这样 \sum_{y \in S} W_y \lt W_x,并在每个顶点上放置一个 S.
打印该操作可以执行的最大次数。
可以证明,无论如何操作,经过有限次迭代后,图上不会出现碎片。
约束
- 所有输入值均为整数。
- 2 \leq N \leq 5000
- 1 \leq M \leq \min \lbrace N(N-1)/2, 5000 \rbrace
- 1 \leq u_i, v_i \leq N
- u_i \neq v_i
- i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
- 1 \leq W_i \leq 5000
- 0 \leq A_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M W_1 W_2 \ldots W_N A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
6 6 1 2 2 3 3 1 3 4 1 5 5 6 9 2 3 1 4 4 1 0 0 0 0 1
示例输出 1
5
在下面的解释中,让 A = (A_1, A_2, \ldots, A_N) 表示顶点上的棋子数量。 最初, A = (1, 0, 0, 0, 0, 1).
考虑执行如下操作:
- 从顶点移除一块 1 并在顶点上各放置一个 2 和 3。现在, A = (0, 1, 1, 0, 0, 1).
- 从顶点移除一块 2。现在, A = (0, 0, 1, 0, 0, 1).
- 从顶点移除一块 6。现在, A = (0, 0, 1, 0, 0, 0).
- 从顶点移除一块 3 并将一块放在顶点上 2。现在, A = (0, 1, 0, 0, 0, 0).
- 从顶点移除一块 2。现在, A = (0, 0, 0, 0, 0, 0).
在此过程中,操作执行了五次,这是可能的最大次数。
示例输入 2
2 1 1 2 1 2 0 0
示例输出 2
0
在此示例输入中,图表上从一开始就没有碎片。
示例输入 3
10 20 4 8 1 10 1 7 5 9 9 10 8 10 7 5 1 4 7 3 8 7 2 8 5 8 4 2 5 1 7 2 8 3 3 4 8 9 7 10 2 3 25 5 1 1 16 5 98 3 21 1 35 39 32 11 35 37 14 29 36 1
示例输出 3
1380