線性規劃與網絡流24題 解題報告
本文正體字版由OpenCC轉換
經過幾天努力終於做完了線性規劃與網絡流24題，同時對網絡流和二分圖的理解也上升到了一個新的高度。把所有題解發上來供大家參考，還請多多指教。
感謝ShingRay發現本文一個錯誤，現已修正。
BYVoid原創 線性規劃與網絡流24題_解題報告Ver 2 (48KB)
另外附上 線性規劃與網絡流24題 (1.90MB) 感謝王曉東老師給我們提供這麼多好題。
幾點說明
- 本題解提供所有問題的解析和大部分問題的C++程序源代碼，以及個別數據的勘誤。
- 本題解只討論問題的分析和建模，具體的實現參照代碼。代碼中所有網絡最大流算法均用Dinic實現。
- 讀者應具備圖論、最短路徑、網絡流的基礎知識，並掌握至少一種網絡最大流和最小費用最大流的算法。
- 建議讀者在閱讀題解前先進行充分的思考，確認無法獨立解決後再看題解。
- 問題8 機器人路徑規劃問題 是個經典難題，暫時還未解決，歡迎大家討論。
- 本題解繫個人原創，請勿商業轉載，非商業轉載請註明來源。
| 問題編號 | 問題名稱 | 問題模型 | 轉化模型 |
| 1 | 飛行員配對方案問題 | 二分圖最大匹配 | 網絡最大流 |
| 2 | 太空飛行計劃問題 | 最大權閉合圖 | 網絡最小割 |
| 3 | 最小路徑覆蓋問題 | 有向無環圖最小路徑覆蓋 | 網絡最大流 |
| 4 | 魔術球問題 | 有向無環圖最小路徑覆蓋 | 網絡最大流 |
| 5 | 圓桌問題 | 二分圖多重匹配 | 網絡最大流 |
| 6 | 最長遞增子序列問題 | 最多不相交路徑 | 網絡最大流 |
| 7 | 試題庫問題 | 二分圖多重匹配 | 網絡最大流 |
| 8 | 機器人路徑規劃問題 | (未解決) | 最小費用最大流 |
| 9 | 方格取數問題 | 二分圖點權最大獨立集 | 網絡最小割 |
| 10 | 餐巾計劃問題 | 線性規劃網絡優化 | 最小費用最大流 |
| 11 | 航空路線問題 | 最長不相交路徑 | 最小費用最大流 |
| 12 | 軟件補丁問題 | 最小轉移代價 | 最短路徑 |
| 13 | 星際轉移問題 | 網絡判定 | 網絡最大流 |
| 14 | 孤島營救問題 | 分層圖最短路徑 | 最短路徑 |
| 15 | 汽車加油行駛問題 | 分層圖最短路徑 | 最短路徑 |
| 16 | 數字梯形問題 | 最大權不相交路徑 | 最小費用最大流 |
| 17 | 運輸問題 | 網絡費用流量 | 最小費用最大流 |
| 18 | 分配問題 | 二分圖最佳匹配 | 最小費用最大流 |
| 19 | 負載平衡問題 | 最小代價供求 | 最小費用最大流 |
| 20 | 深海機器人問題 | 線性規劃網絡優化 | 最小費用最大流 |
| 21 | 最長k可重區間集問題 | 最大權不相交路徑 | 最小費用最大流 |
| 22 | 最長k可重線段集問題 | 最大權不相交路徑 | 最小費用最大流 |
| 23 | 火星探險問題 | 線性規劃網絡優化 | 最小費用最大流 |
| 24 | 騎士共存問題 | 二分圖最大獨立集 | 網絡最小割 |
上次修改時間 2017-05-22