Beyond the Void
BYVoid
線性規劃與網絡流24題 解題報告
本文正體字版由OpenCC轉換

經過幾天努力終於做完了線性規劃與網絡流24題,同時對網絡流和二分圖的理解也上升到了一個新的高度。把所有題解發上來供大家參考,還請多多指教。

感謝ShingRay發現本文一個錯誤,現已修正。

BYVoid原創 線性規劃與網絡流24題_解題報告Ver 2 (48KB)

另外附上 線性規劃與網絡流24題 (1.90MB) 感謝王曉東老師給我們提供這麼多好題。

幾點說明

  1. 本題解提供所有問題的解析和大部分問題的C++程序源代碼,以及個別數據的勘誤。
  2. 本題解只討論問題的分析和建模,具體的實現參照代碼。代碼中所有網絡最大流算法均用Dinic實現。
  3. 讀者應具備圖論、最短路徑、網絡流的基礎知識,並掌握至少一種網絡最大流和最小費用最大流的算法。
  4. 建議讀者在閱讀題解前先進行充分的思考,確認無法獨立解決後再看題解。
  5. 問題8 機器人路徑規劃問題 是個經典難題,暫時還未解決,歡迎大家討論。
  6. 本題解繫個人原創,請勿商業轉載,非商業轉載請註明來源。
問題一覽
問題編號 問題名稱 問題模型 轉化模型
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

相關日誌