CF437C The Child and Toy

儿童节这天，孩子收到了 Delayyy 送的一份玩具作为礼物。然而，这个孩子太调皮了，等不及要把玩具拆掉了。 这个玩具由 $n$ 个部件和 $m$ 条绳索组成。每条绳索连接着两个部件，且任意一对部件至多被一条绳索连接。要拆分这个玩具，孩子必须把所有的部件都拆除。孩子每次只能拆除一个部件，每拆除一个部件会消耗能量。我们定义第 $i$ 个部件的能量值为 $v_i$。孩子在拆除第 $i$ 个部件时，会消耗 $v_{f_1} + v_{f_2} + \dots + v_{f_k}$ 的能量，其中 $f_1, f_2, \dots, f_k$ 表示与第 $i$ 个部件直接相连且尚未被拆除的部件的编号。 请你帮助孩子计算，拆除所有 $n$ 个部件所需要消耗的最小总能量是多少。

第一行包含两个整数 $n$ 和 $m$（$1\leq n\leq 1000$，$0\leq m\leq 2000$）。 第二行包含 $n$ 个整数：$v_1, v_2, \ldots, v_n$（$0\leq v_i\leq 10^5$）。 接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示一条连接部件 $x_i$ 和部件 $y_i$ 的绳索（$1\leq x_i, y_i \leq n；x_i \neq y_i$）。 所有部件从 $1$ 到 $n$ 编号。

输出拆除这个玩具的所有 $n$ 个部件所需消耗的最小总能量。

对于第一个样例，最优拆除顺序之一是： - 首先拆掉第 $3$ 个部件，消耗 $20$ 能量。 - 然后拆掉第 $2$ 个部件，消耗 $10$ 能量。 - 接着拆掉第 $4$ 个部件，消耗 $10$ 能量。 - 最后拆掉第 $1$ 个部件，消耗 $0$ 能量。 因此，孩子一共需要消耗的最小总能量为 $20+10+10+0=40$。 对于第二个样例，无论拆除顺序如何，孩子总共都需要消耗 $400$ 能量。 由 ChatGPT 5 翻译