新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:65536KB
問題 
牛達が航空線を開始した。乗客は牛達である。ミシガン湖の西沿岸に住む牛達にサービスする計画である。毎朝、北の端から南の端であるシカゴに向かい、途中何回も停まる。夕方には北の端に向けて戻る。
毎日の乗客を決定するために、彼らにはあなたの助けが必要である。1からN(1<=N<=10,000)まで番号を付けられた農場には空港がある。(農場1は北端であり、農場Nは南端である。)この日は、K(1<=K<=50,000)組の牛の団体が移動を計画していた。どの団体もある農場から別の農場への移動を計画している。もし必要なら、航空機は団体の一部だけを乗せることも可能である。しかし、一度乗せたからには牛達を目的地に連れて行かなくてはならない。
航空機の容量C(1<=C<=100)と、移動したい牛の団体が与えられるので、目的地に到達することのできる最大の牛の数を求めよ。
入力
1行目はスペースで区切られた3つの整数K,N,Cが与えられる。
2行目からK+1行目までは、それぞれ牛の団体を意味するスペースで区切られた3つの整数S,E,Mが与えられる。M(1<=M<=C)は農場Sから農場Eに移動したいと思っている牛の数である。(SとEは等しくない。)
出力
目的地に到達できる牛の最大数を出力せよ。これは朝に南に向かう牛と、夕方に北に向かう牛の合計数である。
入力の例
4 8 3 1 3 2 2 8 3 4 7 1 8 3 2
出力の例
6
ヒント
入力の例は4つの牛の団体と、8つの農場、3席の航空機である。
出力の例の意味は、朝に2頭の牛を農場1から農場3に乗せ、1頭を農場2から農場8へ、1頭を農場4から農場7へ乗せたものであり、夕方には2頭を農場8から農場3へ乗せたものである。
出典
USACO 2005 October Gold
