プロンプトとコンテキスト
各有向エッジには容量と単位コストがあります。s から t へ、同じフローを持つ解の中でコストが最小となるように、制限値までフローを送ります。残余逆エッジ、負のコスト、多重辺（並行エッジ）、到達不能なシンク、整数オーバーフローを処理しながら、実際のフローとコストを返します。
面接官がテストしていること
- 残余エッジと逆コストを正しく構築できるか。
- 負のエッジがある場合に、逐次最短路法（successive shortest paths）やポテンシャルを使用できるか。
- 最大フローの目的と、タイブレーカーとしての最小コストを区別できているか。
- 計算量、オーバーフロー制限、プロパティベーステストを提示できるか。
回答前に確認すべき質問
容量とコストが整数であるか、負の閉路（negative-cost cycles）が許容されるか、厳密な上限の要件、グラフサイズ、およびコストの境界を確認します。負の閉路が許容される場合は、無制限のコスト削減がモデルの一部であるかどうか、および初期ポテンシャルがどのように取得されるかを明確にします。
30秒の回答フレームワーク
各入力エッジに対して、順方向の残余エッジと、コストを反転させた容量ゼロの逆エッジを追加します。残余グラフ内で s から t への最短路を繰り返し見つけ、制限に達するかパスがなくなるまでそのボトルネックを増加（augment）させます。コストが負になり得る場合は、Bellman-Ford で初期ポテンシャルを計算し、Dijkstra が有効になるようにエッジの重みを再計算（reweight）します。計算量は、通常の最大フローの計算量だけでなく、増加ステップと最短路の実装に依存します。
ステップバイステップの詳細解説
1. 残余エッジの構造
行先、逆エッジのインデックス、残余容量、コストを格納します。フローの増加により、順方向の容量が減少し、逆方向の容量が増加し、フロー×コストが合計に加算されます。逆エッジにより、後のパスで以前の選択を取り消すことが可能になり、これは最適コストを達成するために不可欠です。
2. 最短路とポテンシャル
コストが非負の場合、Dijkstra で十分です。負のコストがあり、負の閉路がない場合は、頂点ごとにポテンシャルを維持し、被約コスト（reduced costs）を使用して最短路を計算してから、ポテンシャルを更新します。負のエッジを含むグラフに通常の Dijkstra を直接適用してはいけません。
3. 増加と終了条件
増加量は、残りの制限、パスのボトルネック、およびバッチ上限の最小値です。パスが存在しなくなったら停止して実際のフローを返します。厳密な制限が要求されている場合は、実行不可能（infeasibility）を報告します。幅の広い整数型を使用し、コストを累積する前に乗算のオーバーフローを確認します。
質の高い模範解答
残余エッジを隣接リストに格納し、順方向と逆方向のペアを一緒に追加します。メインループでは、正の容量を持つエッジ間で s から t への最短路を見つけ、それを増加させてコストを更新します。非負コストには Dijkstra が機能します。負のコストがあり負の閉路がない場合は、初期ポテンシャルを計算し、被約コストを非負に保ちます。各増加は、残りの需要とパスのボトルネックによって制限します。シンクが到達不能になった場合は、実際のフローを返し、未達のターゲットを実行不可能としてマークします。テストでは、逆方向のキャンセル、多重辺、容量ゼロ、負のコスト、非連結グラフ、部分フロー、負の閉路の前提条件、および大きなコストによるオーバーフローをカバーします。このモデルは OR-Tools の最小費用流の定式化と一致しますが、計算量には頂点、エッジ、および増加の要因を挙げる必要があり、数値容量において自動的に多項式時間になるわけではありません。
よくある間違い
- 逆エッジを忘れる、または反転したコストではなく正のコストを割り当てること。
- 残余エッジが負のコストを持つ可能性があるときに Dijkstra を直接実行すること。
- 正当な理由なく、最短路ごとに1ユニットしか増加させないこと。
- 最大フローと最小コストを区別のない単一のソートキーとして扱うこと。
- 大きな「容量×コスト」の値を狭い整数型に累積すること。
フォローアップの質問と回答
なぜ逆エッジによって以前の選択を修正できるのですか？
以前に送られたフローを取り消すことを表し、そのフローのコストを反転（相殺）させるためです。後の最短路がそれを利用して解を再編成し、総コストを下げることができます。
どのような場合に Bellman-Ford が必要になりますか？
初期の残余グラフに負のコストのエッジがあるものの負の閉路がない場合、Bellman-Ford または同等の方法を使用して初期ポテンシャルを計算します。その後、非負の被約コストによって Dijkstra の適用が可能になります。
要求されたフローに達しない場合はどうなりますか？
処理を停止し、実際のフローとコストを明示的な実行不可能（infeasible）の結果とともに返します。ビジネス要件としてターゲットが必須である場合、呼び出し元は部分フローを成功として扱うのではなく、ロールバックするか代替ネットワークを選択する必要があります。