如何實作最小費用最大流？
題目與使用情境
網路每條邊有容量與單位費用，要求從 s 到 t 傳送最多 limit 的流量，並在流量相同的方案中費用最小。實作需要回傳實際流量與費用，處理反向殘量邊、負費用、平行邊、不可達與整數溢位。
面試官考察什麼
- 是否正確建立殘量網路與反向邊費用。
- 能否用連續最短增廣路或勢能重標定處理負邊。
- 是否區分最大流量目標與最小費用次目標。
- 能否提出複雜度、溢位邊界與性質測試。
作答前的釐清問題
確認容量與費用是否為整數、是否允許負費用環、是否要求精確 limit、圖規模與費用上界。若有負費用環，要說明模型是否允許無界降費，以及初始勢能如何求得。
30 秒回答框架
每條輸入邊建立正向容量和反向容量為零的殘量邊，反向費用取相反數。反覆在殘量網路尋找 s 到 t 的最短路，沿路增廣瓶頸流量，直到達到 limit 或不存在路徑。若邊費用可能為負，先用 Bellman-Ford 求初始勢能，之後用勢能重標定讓邊費用非負，再用 Dijkstra。總複雜度取決於增廣次數與最短路實作，不能只報普通最大流複雜度。
分步驟深入解答
1. 殘量邊結構
邊記錄終點、反向索引、剩餘容量與費用。增廣時減少正向容量、增加反向容量；費用乘以增廣流量累加。反向邊允許演算法撤銷早期選擇，是費用最優的關鍵。
2. 最短路與勢能
若所有費用非負，Dijkstra 足夠。存在負費用但沒有負環時，維護每個點的勢能，使用重標定後費用計算最短路，再更新勢能。若初始費用含負值，不能直接把普通 Dijkstra 當作正確演算法。
3. 增廣與停止
每次增廣量是剩餘 limit、路徑瓶頸與可選批量的最小值。路徑不存在時停止並回傳目前流量；若必須達到 limit，則回報不可行。費用用足夠寬的整數型別，並在加法前檢查乘法溢位。
高品質示範回答
我會用鄰接表保存殘量邊，每次 addEdge 同時加入正向與反向邊。主迴圈在殘量容量為正的圖上尋找最短 s 到 t 路徑，沿路增廣並更新費用。無負費用時用 Dijkstra；有負費用但無負環時先求初始勢能，再用 reduced cost 保持非負。每輪把增廣量限制為目標剩餘、路徑瓶頸與邊容量。無法繼續時回傳實際流量；若小於目標則標記不可行。測試涵蓋反向撤銷、平行邊、零容量、負費用、斷開圖、達到部分流量、負環約束與大費用溢位。最小費用最大流與 OR-Tools 的模型一致，但具體複雜度要按增廣次數、節點與邊數說明，不能假設總是多項式於數值容量。
常見錯誤
- 忘記加入反向邊或把反向費用設為正數。
- 存在負費用邊時直接使用 Dijkstra。
- 找到最短路後只增廣一單位，造成不必要的執行時間。
- 把「最大流」與「達到目標流量的最小費用」混成一個排序條件。
- 用窄整數累計費用，忽略大容量乘費用的溢位。
追問及應對
為什麼反向邊能修正之前的選擇？
反向邊代表撤回已傳送的流量，並把相應費用取反。後續最短路可以走反向邊，重新安排流量後得到較低總費用。
什麼時候需要 Bellman-Ford？
初始殘量圖含負費用邊且沒有負環時，需要它或等價方法計算初始勢能；之後 reduced cost 非負即可使用 Dijkstra。
如果目標流量達不到怎麼辦？
停止並回傳實際流量與費用，同時明確不可行。若業務必須滿足目標，應在呼叫層回滾或選擇備援網路，不能把部分流量冒充成功。