問題
N 個のタンクと M 本のパイプがあります。
j 本目のパイプはタンク Aj からタンク Bj の方向に毎秒 Cj リットルまでの水を流すことができます。
タンク 1 からタンク N まで毎秒最大何リットルの水を流すことができますか。
ただし、タンクに水をためることはできません。
[制約]
🔹2≦N≦400
🔹1≦M≦4000
🔹0≦Cj≦5000
🔹答えは5000以下の整数
解き方
この問題は最大流問題と呼ばれる、グラフ上の最大流量を求める問題の一種です。
まず、各タンクを頂点とし、各パイプを辺とするグラフを作成します。
辺の容量はそのパイプが運べる最大の水の量 Cj とします。
このグラフに対して、最大流量を求めるアルゴリズムを実行することで、タンク 1 からタンク N への最大流量を求めることができます。
有名な最大流アルゴリズムには、Ford-Fulkerson アルゴリズムや、Dinic アルゴリズムがあります。
ソースコード
[Google Colaboratory]
1 | #--------- 入力例1 ---------- |
このソースコードは、最大フロー問題を解くためにフォード・ファルカーソン法を実装したものです。
フォード・ファルカーソン法は、エッジのフロー量を増加させることによって最大フローを求めるアルゴリズムです。
このコードでは、最大フロー問題を解くために、FordFulkersonというクラスを定義しています。
このクラスは、グラフの構造を保持するための変数graphと、最大フローを求めるための関数max_flowを持ちます。
まず、入力例1のデータに従ってグラフを構築します。
このグラフは、defaultdictを用いて辞書形式で表現されており、各頂点にはその頂点に接続するエッジ(辺)の情報が保持されています。
次に、最大フローを求めるために、dfs関数を定義しています。
この関数は、sからtへの最大フローを求めるために、深さ優先探索を実行します。
具体的には、現在の頂点から次の頂点へのパスを探索し、最大フローを更新していきます。
最後に、max_flow関数を呼び出すことで、sからtへの最大フローを求めることができます。
この関数は、whileループを用いて、dfs関数を反復的に呼び出して最大フローを求めます。
[実行結果(入力例1)]
8
入力例1の場合、タンク 1 からタンク N へ毎秒最大 8 リットルの水を流すことができることが分かりました。