本文正體字版由OpenCC轉換

【問題分析】

有向無環圖最小路徑覆蓋，可以轉化成二分圖最大匹配問題，從而用最大流解決。

【建模方法】

構造二分圖，把原圖每個頂點i拆分成二分圖X，Y集合中的兩個頂點Xi和Yi。對於原圖中存在的每條邊(i,j)，在二分圖中連接邊(Xi,Yj)。然後把二分圖最大匹配模型轉化爲網絡流模型，求網絡最大流。

最小路徑覆蓋的條數，就是原圖頂點數，減去二分圖最大匹配數。沿着匹配邊查找，就是一個路徑上的點，輸出所有路徑即可。

【建模分析】

對於一個路徑覆蓋，有如下性質：

1、每個頂點屬於且只屬於一個路徑。 2、路徑上除終點外，從每個頂點出發只有一條邊指向路徑上的另一頂點。

所以我們可以把每個頂點理解成兩個頂點，一個是出發，一個是目標，建立二分圖模型。該二分圖的任何一個匹配方案，都對應了一個路徑覆蓋方案。如果匹配數爲0，那麼顯然路徑數=頂點數。每增加一條匹配邊，那麼路徑覆蓋數就減少一個，所以路徑數=頂點數 - 匹配數。要想使路徑數最少，則應最大化匹配數，所以要求二分圖的最大匹配。

注意，此建模方法求最小路徑覆蓋僅適用於有向無環圖，如果有環或是無向圖，那麼有可能求出的一些環覆蓋，而不是路徑覆蓋。

最小路徑覆蓋問題
問題描述: 給定有向圖 G=(V,E)。設 P 是 G 的一個簡單路(頂點不相交)的集合。如果 V 中每個頂點恰好在 P 的一條路上,則稱 P 是 G 的一個路徑覆蓋。P 中路徑可以從 V 的任何一個頂 點開始,長度也是任意的,特別地,可以爲 0。G 的最小路徑覆蓋是 G 的所含路徑條數最少 的路徑覆蓋。
設計一個有效算法求一個有向無環圖 G 的最小路徑覆蓋。 提示:設 V={1,2,o ,n},構造網絡 G1=(V1,E1)如下:
V1 = {x0 , x1 ,, xn }» {y0 , y1 ,, yn },
E 1 = {( x 0 , x i ) : i Œ V } » {( y i , y 0 ) : i Œ V } » {( x i , y j ) : ( i . j ) Œ E } 每條邊的容量均爲 1。求網絡 G1 的( x0 , y0 )最大流。
 ́編程任務: 對於給定的給定有向無環圖 G,編程找出 G 的一個最小路徑覆蓋。  ́
數據輸入: 由文件 input.txt 提供輸入數據。文件第 1 行有 2 個正整數 n 和 m。n 是給定有向無環圖G 的頂點數,m 是 G 的邊數。接下來的 m 行,每行有 2 個正整數 i 和 j,表示一條有向邊(i,j)。  ́
結果輸出:
程序運行結束時,將最小路徑覆蓋輸出到文件 output.txt 中。從第 1 行開始,每行輸出 一條路徑。文件的最後一行是最少路徑數。
輸入文件示例
input.txt
11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11
輸出文件示例
output.txt
1 4 7 10 11
2 5 8
3 6 9
3

上次修改時間 2017-02-03