ネットワーク最大流

整数容量ネットワークの最大流・最小カットと入力有向辺ごとの流量を確認します。

例の値が入力されています。直接確認するか、値を変更してみてください。

入力はブラウザで処理されます。再読み込みすると例の値に戻ります。

結果

使い方と例

Residual augmentation; max flow=min cut

既定ネットワークの最大流は7で、最小カットの始点側はSとAです。 入力順の辺流量は4, 3, 4, 3です。

ノード30個・辺100本以内で、容量は整数0〜1000000です。 最大流の配分は一意とは限らず、残余経路は入力順に探索します。

よくある質問

最大流の並行辺はどう扱いますか?

並行辺・逆向き辺を別々に保持します。入力順の各行に容量と流量を表示し、自己ループの流量は0です。

最小カットの始点側一覧とは?

これ以上増流できない時点で、残余辺を通って始点から到達できるノード集合です。

計算基準と参考資料

計算基準の確認: · 計算・検証原則 · エラー報告