お風呂は気持ちいい

原案　大村

問題概要

・お風呂を沸かす魔法を使いたいので、魔導石の近くにいる魔法使いから、他の魔法使い経由で魔力を送ってもらいたい。

・魔法を起動できるだけの魔力を送ってもらえるかを判定してください。

部分点

・制約 from - 1 = to ということは、

魔法使いは一列に並んでいて、隣の人にしか渡せないというような状況を考えれば良い。

・魔導石の近くにいる人から自分にむかって、capの最小値を取ればよい。

想定解法

フローを流せ！全部だ！

（ちゃんとした説明は、あり本とかみてください）

フロー：最大流　基本方針

・SからGまでフローを流したいときに、

①深さ優先探索でパスを探す。

②見つかったら流せるだけ流す。

　見つからなかったら終了。

​

フロー：最大流　情報の持ち方

・各辺が流せる量がどれだけ残っているかを保持しておく。

・また、a→bに１流れているときは、新しいフローを流す時に、b→aに1流すことができるので、その情報も保持しておく。

想定解法

・このようにして、魔導石の近くにいる魔法使いの誰からも、アスナさんに向かって魔力を送れなくなるまでフローを流します。

・この時流せる量と、お風呂を沸かすのに必要な魔力の量を比べて、答えます。

元ネタ

・ソードアートオンラインのアスナが、ゲーム世界の中で初めてお風呂に入ったシーンで、あまりにも気持ちよさそうだったため登場させました。

（原案は魔法を使うだけでした）

この修正が直前だったため問題文の整合が取れなくなっている箇所がありました、申し訳ありません