OI题库

【题目描述】

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

沿着湖岸，有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