OI题库

【题目描述】

某国有N个城镇，M条铁路。所有的铁路都是单向的，并且铁路不行成环。必须按照如下事实选择最好的列车运行线：

运行线是指火车经过的一个城镇序列，必须满足如下要求：

1）每条铁路最多属于一条列车运行线

2）每个城镇最多被一条列车运行线通过（通过包括作为起点或终点）

3）每个城镇至少被一条列车运行线通过

4）列车运行线的数量应尽量小

并且，每条铁路都需要花钱维护，第i条铁路需要每年花费c[i]元来检修。这是该国总统决定安排列车运行线使得维护运行线上铁路的总费用最小。当然，这个任务被交给了你。

【输入格式】

输入文件的第一行有两个正整数N，M（1<=N<=100,0<=M<=1000）.接下来的M行描述了M条铁路。

每一行有三个整数a[i],b[i]和c[i]（1<=a[i],b[i]<=N,a[i]≠b[i]），即该条线路的起点，终点和维护费用（0<=c[i]<=1000）.因为铁路是单向的，火车只能从a[i]开到b[i]。两个城镇之间至多有一条铁路。

【输出格式】

输出一行两个正整数，即最少的运行线数量，和在此前提下最少的总花费。

【样例输入】

4 4

1 2 1

1 3 2

3 4 2

2 4 2

【样例输出】

2 3

【提示】

本题的输出格式和SGU上原题有所区别，在这里不要求输出答案。

【来源】

SGU 252 Railway Communication

作者:Sergey Simonchik

来源:Petrozavodsk Summer Training Sessions 2004

日期:August 25, 2004