線性規劃與網絡流24題-飛行員配對方案問題
本文正體字版由OpenCC轉換
【問題分析】
二分圖最大匹配問題。
【建模方法】
在二分圖的基礎上增加源S和匯T。 1、S向X集合中每個頂點連一條容量爲1的有向邊。 2、Y集合中每個頂點向T連一條容量爲1的有向邊。 3、XY集合之間的邊都設爲從A集合中的點到B集合之中的點，容量爲1的有向邊。
求網絡最大流，流量就是匹配數，所有滿流邊是一組可行解。
【建模分析】
基本的二分圖最大匹配，可以直接用匈牙利算法或Hopcroft_Karp算法解決，更一般的方法是網絡最大流。
飛行員配對方案問題
問題描述: 第二次世界大戰時期,英國皇家空軍從淪陷國徵募了大量外籍飛行員。由皇家空軍派出的每一架飛機都需要配備在航行技能和語言上能互相配合的 2 名飛行員,其中 1 名是英國飛 行員,另 1 名是外籍飛行員。在衆多的飛行員中,每一名外籍飛行員都可以與其他若干名英 國飛行員很好地配合。如何選擇配對飛行的飛行員才能使一次派出最多的飛機。對於給定的 外籍飛行員與英國飛行員的配合情況,試設計一個算法找出最佳飛行員配對方案,使皇家空 軍一次能派出最多的飛機。
編程任務:
對於給定的外籍飛行員與英國飛行員的配合情況,編程找出一個最佳飛行員配對方案, 使皇家空軍一次能派出最多的飛機。
數據輸入:
由文件 input.txt 提供輸入數據。文件第 1 行有 2 個正整數 m 和 n。n 是皇家空軍的飛行 員總數(n ́結果輸出:
程序運行結束時,將最佳飛行員配對方案輸出到文件 output.txt 中。第 1 行是最佳飛行 員配對方案一次能派出的最多的飛機數 M。接下來 M 行是最佳飛行員配對方案。每行有 2 個正整數 i 和 j,表示在最佳飛行員配對方案中,飛行員 i 和飛行員 j 配對。
如果所求的最佳飛行員配對方案不存在,則輸出‘No Solution!’。
上次修改時間 2017-02-03