#P1669. [USACO04DEC] Bad Cowtractors S
[USACO04DEC] Bad Cowtractors S
题目描述
奶牛贝茜被雇去建设 个牛棚间的互联网。她已经勘探出 条可建的线路,每条线路连接两个牛棚,而且会花费 。农夫约翰吝啬得很,他希望建设费用最少甚至他都不想给贝茜工钱。贝茜得知工钱要告吹,决定报复。她打算选择建一些线路,把所有牛棚连接在一起,让约翰花费最大。但是她不能造出环来,这样约翰就会发现。
输入格式
第 行:,。
第 到 行:三个整数,表示一条可能线路的两个端点和费用。
输出格式
一行,表示最大的花费。如果不能建成合理的线路,就输出 。
5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17
42
提示
,,。