Skip to content

11337: 【原1337】欢总的决裂

题目

题目描述

author: cloudygoose 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1337

Description

一般人换女朋友,都是一个一个换的。但对于欢总来说,换女朋友都是一批一批换的,所以坊间一直称欢总为“换总”。
现在又到了月末,欢总又开始考虑换女友的事情了。他要与N个MM分手,对于第i个MM,欢总有两种选择,一种是欢总亲自去分手,这样欢总会吃Ai记耳光,或者,欢总可以让MMj去代为 分手,但这样欢总会从MMj处多吃Gji记耳光。欢总能洞悉女人的心理,他知道Ai和Gji的数值。
另外,由于女孩间的一些奇怪约定,叫i去通知j获得的耳光数和叫j去通知i获得的耳光数是相等的。换句话说,题目中的边是无向边。
欢总当然希望吃的耳光越少越好,于是他决定编一个程序,求出在所有MM都被欢总直接或间接分手的情况下,所吃的最少的耳光数。
对于没看懂题目的同学,说白了,就是找一颗以欢总为跟的带权的分手树。 夜静静的,风悄悄的,欢总写好了N封分手信出发了,夕阳西下,断肠人在天涯。

Input Format

第一行有两个数,N和M。
第二行有N个数,是Ai。 接下来M行,描述M条边,每行的格式是Ex,Ey,Ec,表示让Ex通知Ey或Ey通知Ex会吃到Ec记耳光。
数据中所有数都是正整数,且所有数字<=1000。
题目输入的边不会重复出现。

Output Format

一个数,表示欢总所吃的最少的耳光数。

Sample Input

3 3
458 443 309 
1 2 320
1 3 173
2 3 151

Sample Output

633

Explaination

欢总亲自通知3号MM,然后让3号MM通知1号和2号MM。

Data Scale

50%: 0 < n <= 10
100%: 0 < n <= 500

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!