競技プログラムの問題を自作してみました。
問題
今年は渇水で農業村Ａは水資源の分配を考えなくてはいけない。
水源0から畑へ水を供給するのだが、全部の畑に供給はできない。
ｒ枚の畑までしか水を供給できないので供給先を選ばなくてはいけない（水の消費量はどの畑も同じ）。
水源と畑には0～ｎまでの重複のない番号が付いており、水路は。
畑か水源が、点。
点同士をつなぐ水路が線であらわされ、全体は木構造で表現され水源は点0のみである。
各畑に水が供給されたときの収穫量がわかっている。
収量が最大になるように水を分配した時の総収穫量を答えよ。
注
ある遠くの畑に水を供給する場合、そこまでの途中にある畑もすべて水を消費するものとする。
（つまり水源を根元とする木構造から水を供給する部分木を決定せよということになる）
データは以下の通り与えられる。
一行目に畑の数ｎ、畑をつなぐ水路の数ｍ、水を供給できる畑の枚数ｒの3つの変数。
2行目からｎ行にわたり、畑の番号niの収穫量ai
その次ｍ行にわたり、畑と畑、畑と水田のつながりの水路データが畑（または水田の）２つの数字で与えられる。
サンプルインプット
4 4 3
1 7
2 2
3 8
4 10
0 1
0 2
1 3
1 4
最終更新：2015年01月30日 01:12
