[SGU206]道路

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file sgu206roads.in Output file sgu206roads.out

【题目描述】

一个遥远的王国有m条双向道路连接着n个城市,两座城市之间有可能有不止一条道路。m条道路中有n-1条石头路,  m-n+1条泥土路,任意两个城市之间有且仅有一条完全用石头路连接起来的道路。

每条道路都有一个唯一确定的编号,其中石头路编号为1..n-1,泥土路编号为n..m。每条道路都需要一定的维护费,其中第i条道路每年需要Ci的费用来维护。最近该国国王准备只维护部分道路以节省费用。但是他还是希望人们可以在任两个城市间互达。

国王需要你提交维护每条道路的费用,以便他能让他的大臣来挑选出需要维护的道路,使得维护这些道路的费用是最少的。

尽管国王不知道走石头路和走泥土路的区别,但是对于人民来说石头路似乎是更好的选择。为了人民的利益,你希望维护的道路是石头路。这样你不得不在提交给国王的报告中伪造维护费用。你需要给道路i伪造一个费用Di,使得这些石头路能够被挑选。为了不让国王发现,你需要使得真实值与伪造值的差值和尽量小。

国王的大臣当然不是白痴,全部由石头路组成的方案如果是一种花费最小的方案,那么他会选择这种方案。

求出真实值与伪造值的差值和的最小值。

【输入格式】

输入文件的第一行有两个整数N,M(2<=N<=60,N-1<=M<=400)。

接下来的M行每行有三个整数ai,bi,ci,即这条道路的两个端点(1<=ai,bi<=N,ai≠bi),和维护这条路的费用(1<=ci<=10000).

【输出格式】

输出一行一个正整数,即真实值与伪造值的差值和f的最小值。

【样例输入】

4 5

4 1 7

2 1 5

3 4 4

4 2 5

1 3 1

【样例输出】

6

【提示】

这里的输出格式和SGU上的原题不同,原题中要求输出方案

【来源】

SGU 206 Roads

作者:Andrew Stankevich

来源:Petrozavodsk Summer Trainings 2003

日期:2003-08-23