bzoj#P1577. [Usaco2009 Feb]庙会捷运Fair Shuttle
[Usaco2009 Feb]庙会捷运Fair Shuttle
题目描述
公交车一共经过 个站点,从站点 一直驶到站点 。 群奶牛希望搭乘这辆公交车。第 群牛一共有 只。
他们希望从 到 去。 公交车只能坐 只奶牛。而且不走重复路线,请计算这辆车最多能满足多少奶牛的要求。 注意:对于每一群奶牛,可以部分满足,也可以全部满足,也可以全部不满足。
输入格式
第 行: 三个整数:,由空格隔开。
第 行:第 行给出第 组奶牛的信息:,由空格隔开。
输出格式
共一行:可以在庙会乘坐捷运的牛的最大头数。
8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1
10
数据规模与约定
对于 的数据,,,,。
提示
捷运可以把 头奶牛从展台 送到展台 , 头奶牛从展台 到展台 , 头奶牛从展台 到展台 , 头奶牛从展台 送到展台 ,一头奶牛从展台 送到展台 ,一头奶牛从 送到 。
题目来源
Usaco 2009 Feb Gold