[USACO Oct05]奶牛航班

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 cowflight.in Output file cowflight.out

【题目描述】

为了表示不能输给人类,农场的奶牛决定成立一家航空公司。她们计划每天早晨,从密歇根湖湖岸的最北端飞向最南端,晚上从最南端飞向最北端。在旅途中,航空公司可以安排飞机停在某些机场。她们需要你帮助来决定每天携带哪些乘客。

沿着湖岸,有N(1<=N<=10000)个由北至南编号为1到N的农场。每个农场都有一个机场。这天,有K(1<=K<=50000)群牛想要乘坐飞机旅行。每一群牛想要从一个农场飞往另一个农场。航班可以在某些农场停下带上全体或部分的牛。奶牛们登机后会一直停留直至达到目的地。

提供给你飞机的容量C(1<=C<=100),同时提供给你想要旅行的奶牛的信息,请你计算出这一天的航班最多能够满足几只奶牛的愿望。

【输入格式】

第1行:3个用空格隔开的整数K,N,C.

第2到K+1行:每一行有3个用空格隔开的整数S,E,M。表示有M只奶牛想从农场S乘飞机到农场E。

【输出格式】

输出一行一个正整数,既可以完成旅行的奶牛数量的最大值。

【样例输入】

4 8 3

1 3 2

2 8 3

4 7 1

8 3 2

【样例输出】

6

【提示】

样例说明:

3群想要旅行的奶牛,8个农场,飞机上有3个座位。早晨,飞机把2只牛从1带到3,1只牛从2带到8,1只牛从4带到7.晚上,航班把2只牛从8带到3.

【来源】

Hal Burch,2004

USACO Oct05