返回信息流幼儿园发玩具了，小朋（sha）友（bi）们今天好开（shang）心（xing）啊。
题目描述
小朋友有n个玩具和m条绳子，每条绳子连着两个玩具，每两个玩具之间最多连一条绳子。小朋友要取某个玩具，就要消耗能量，这个能量就是跟这个玩具直接相连的其他玩具的能量值（已经被取走的玩具就不算相连了）。如下面样例1,4个玩具和3条绳子，每个玩具的能量值分别为10,20,30,40，其中1和4相连，1和2相连，2和3相连。小朋友如果要取光所有玩具，可以先取玩具3，这样就要消耗跟3直接相连的2的能量，花费20能量；然后取玩具2，这样就要消耗玩具1的能量值，花费10能量；然后取玩具4，也花费10；最后取玩具1，因为没有玩具与之相连了，不用花费能量。所以总共需要花费20+10+10+0能量，这也是取走所有玩具花费的最少能量。
输入输出格式
输入格式：
给你n个玩具和m条绳子，每个玩具的能量值（n个数字）以及玩具间相连的情况（m行，每行两个数字a,b，表示玩具a与玩具b相连），问花费最少能量是多少？
输出格式：
输出最少花费。
输入输出样例
输入样例#1：
4 3
10 20 30 40
1 4
1 2
2 3
输出样例#1：
40
说明
玩具编号为1到n，1<=n<=1000, 0<=m<=2000, 能量值为[0, 100000]之间的整数。
这是一条镜像帖。来源：北邮人论坛 / java / #58142同步于 2017/11/23
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Java机器人发帖
向Java高手求解编程题，一点思路都没有
zeze107
2017/11/23镜像同步10 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
提个思路,不知道是否理解了题主意思:
每次取玩具,可以理解为:将该玩具和与其相连的所有玩具连接断开,且消耗能量为对端玩具的能量值.
于是,整个过程中,可以理解为所有绳子都要且仅要断开一次,断开所花能量为某一端玩具的能量值.
为了使总能量值最小,那么我们把玩具能量值排个序,从大到小依次取走,就保证了断开每个绳子所需要的能量值都最小.
这不是硬币找零嘛，我有写过[ema0]
http://blog.csdn.net/yuan487639/article/details/76089965
有个平方复杂度的思路，首先可以得到一个map，这个map的键是玩具id，值是和这个玩具有关联的玩具id。然后现在需要做的就是每一步从当前这个map中选择拿掉某个玩具，拿掉玩具的同时更新map中状态（就是拿掉某个玩具之后可能会导致map中其他玩具的值发生变化）。然后拿这个玩具的策略就是，拿掉玩具的花费和对map影响值相减最小的那个就是当前的选择
上面的策略说的不清楚，举个例子，比如说现在有个map中的一个键值是1->2，4(1,2,3,4的能量对应是10，20，30，40)，那么拿掉1的花费就是（20+40）-（10+10）=40,同样算出拿掉2，3，4的花费。选最小的那个就是当前的选择，同时选择了之后还要更新map的状态，比如选了1之后，其他的键值对的值中如果有1的要去掉
要取到所有玩具就是要把m条绳依次拿掉，去掉一条绳子消耗的能量是所连接的两个玩具中一个的能量，要使消耗能量最少，只要保证每个拿掉一根绳子时消耗的是能量较小玩具的能量就行了，所以答案就是所有绳子连接的玩具能量较小的总和
如果绳子可以断开，那例一中先取2，消耗与2连接的1的能量10，此时3断开，没有玩具相连，不消耗能量，再取4，消耗与4相连的1的能量10，最后取1，没有玩具相连了不消耗能量。总和为20.
如果绳子可以取完中间玩具后依旧相连，那例一中先取2，消耗1的能量10，此时3,1；4,1相连，取3、4分别消耗10能量，总和为30
而题目的例1中结果为40，看来以上两种想法都不对。
【 在 zeze107 的大作中提到: 】
幼儿园发玩具了，小朋（sha）友（bi）们今天好开（s...
忘了这是哪家的笔试题了。我记得搜到的答案不算太难。其他记不住了。