103415: [Atcoder]ABC341 F - Breakdown

Problem Statement

You are given a simple undirected graph consisting of $N$ vertices and $M$ edges. For $i = 1, 2, \ldots, M$, the $i$-th edge connects vertices $u_i$ and $v_i$. Also, for $i = 1, 2, \ldots, N$, vertex $i$ is assigned a positive integer $W_i$, and there are $A_i$ pieces placed on it.

As long as there are pieces on the graph, repeat the following operation:

• First, choose and remove one piece from the graph, and let $x$ be the vertex on which the piece was placed.
• Choose a (possibly empty) set $S$ of vertices adjacent to $x$ such that $\sum_{y \in S} W_y \lt W_x$, and place one piece on each vertex in $S$.

Print the maximum number of times the operation can be performed.

It can be proved that, regardless of how the operation is performed, there will be no pieces on the graph after a finite number of iterations.

Constraints

• All input values are integers.
• $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$

Input

The input is given from Standard Input in the following format:

$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$

Output

Print the answer.

Sample Input 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

Sample Output 1

5

In the following explanation, let $A = (A_1, A_2, \ldots, A_N)$ represent the numbers of pieces on the vertices. Initially, $A = (1, 0, 0, 0, 0, 1)$.

Consider performing the operation as follows:

• Remove one piece from vertex $1$ and place one piece each on vertices $2$ and $3$. Now, $A = (0, 1, 1, 0, 0, 1)$.
• Remove one piece from vertex $2$. Now, $A = (0, 0, 1, 0, 0, 1)$.
• Remove one piece from vertex $6$. Now, $A = (0, 0, 1, 0, 0, 0)$.
• Remove one piece from vertex $3$ and place one piece on vertex $2$. Now, $A = (0, 1, 0, 0, 0, 0)$.
• Remove one piece from vertex $2$. Now, $A = (0, 0, 0, 0, 0, 0)$.

In this procedure, the operation is performed five times, which is the maximum possible number of times.

Sample Input 2

2 1
1 2
1 2
0 0

Sample Output 2

0

In this sample input, there are no pieces on the graph from the beginning.

Sample Input 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

Sample Output 3

1380

问题描述

你被给定一个包含$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