← 返回题目列表

AtCoder · abc341_f

I. 故障

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

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