问题1001--小朋友的玩具

1001: 小朋友的玩具

时间限制: 1 Sec  内存限制: 128 MB
提交: 174  解决: 111
[提交] [状态] [讨论版] [命题人:]

题目描述

小朋友有n个玩具和m条绳子,每条绳子连着两个玩具,每两个玩具之间最多连一条绳子。小朋友要取某个玩具,就要消耗能量,这个能量就是跟这个玩具直接相连的其他玩具的能量值(已经被取走的玩具就不算相连了)。如下面样例1,4个玩具和3条绳子,每个玩具的能量值分别为10,20,30,40,其中14相连,12相连,23相连。小朋友如果要取光所有玩具,可以先取玩具3,这样就要消耗跟3直接相连的2的能量,花费20能量;然后取玩具2,这样就要消耗玩具1的能量值,花费10能量;然后取玩具4,也花费10;最后取玩具1,因为没有玩具与之相连了,不用花费能量。所以总共需要花费20+10+10+0能量,这也是取走所有玩具花费的最少能量。

输入

给你n个玩具和m条绳子,每个玩具的能量值(n个数字)以及玩具间相连的情况(m行,每行两个数字a,b,表示玩具a与玩具b相连),问花费最少能量是多少?

玩具编号为1n1<=n<=1000, 0<=m<=2000, 能量值为[0, 100000]之间的整数。

输出

出最少花费。

样例输入 Copy

4 3
10 20 30 40
1 4
1 2
2 3

样例输出 Copy

40

提示

input

4 4
100 100 100 100
1 2
2 3
2 4
3 4

output

400

 

input

7 10
40 10 20 10 20 80 40
1 5
4 7
4 5
5 2
5 7
6 4
1 6
1 3
4 3
1 4

output

160

来源/分类

cf437C