Score: $475$ points

问题描述

你被给予一个由 $N$ 个顶点和 $M$ 条边构成的简单无向图。对于 $i = 1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。同时，对于 $i = 1, 2, \ldots, N$，顶点 $i$ 被赋予了一个正整数 $W_i$，并在其上放置了 $A_i$ 个棋子。

只要图上还有棋子，就重复以下操作：

• 首先，选择并移除图上的一个棋子，并令 $x$ 为该棋子所在的顶点。
• 然后选择一个（可能为空）与顶点 $x$ 相邻的顶点集合 $S$，满足 $\sum_{y \in S} W_y < W_x$，并在 $S$ 中每个顶点上各放置一个棋子。

输出能够进行上述操作的最大次数。

可以证明，无论怎样执行操作，在有限次迭代后，图上将不再有棋子。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:35:22