Mato is No.1

有向無環圖的最小路徑覆蓋問題包括兩種（設G是一個有向無環圖，S是G的一個路徑集合）：
（1）最小點路徑覆蓋：滿足對于G中所有的點i，i在S中的一條路徑中出現，且只在S中的一條路徑中出現，求S的最小容量；
（2）最小邊路徑覆蓋：滿足對于G中所有的邊E，E在S中的一條路徑中出現，且只在S中的一條路徑中出現，求S的最小容量；

（1）最小點路徑覆蓋：
建立一個新圖，將G中的每個點i在新圖中拆成兩個點i'、i''，若G中存在邊<i, j>則在新圖中連邊<i', j''>，顯然新圖是一個二分圖，求其最大匹配，則(N-新圖最大匹配的值)就是最小點路徑覆蓋值。
時間復雜度：O(NM)（Hungary算法）

（2）最小邊路徑覆蓋：
對于圖中的每個點i，設D[i]為(i的入度-i的出度)的值，按照D[i]將圖中的點分類：D[i]<0的稱為“入少出多”的點，D[i]>0的稱為“出少入多”的點，D[i]=0的稱為“入出相等”的點。則有：
定理 有向無環圖中最小邊路徑覆蓋的值等于圖中所有“入少出多”的點的D值之和。
證明：
其實只需證明：對于一個至少有一條邊的有向無環圖，必然存在一條路徑，其起點是“入少出多”的點，終點是“出少入多”的點，所有中間點都是“入出相等”的點（只要不斷的在圖中找到并刪去這條路徑，直到圖中無邊為止）。
首先，由于圖中無環，一定存在“入少出多”的點和“出少入多”的點。
然后，假設圖中所有“入少出多”的點的后繼（注意：后繼和后代是不同的，一個點的后代包括這個點的所有后繼、所有后繼的后繼、所有后繼的后繼的后繼……）也都是“入少出多”的點，則圖中所有“入少出多”的點構成了一個閉合子圖，在這個閉合子圖中，由于所有的點都是“入少出多”的，整個子圖的入度之和必然大于出度之和，這是不可能的（有向圖中的所有點入度之和必然等于所有點出度之和），故可得：圖中必然存在至少一個“入少出多”的點，它有不是“入少出多”的后繼。
這樣，在這些擁有不是“入少出多”的后繼的點中選擇一個點i，將其作為路徑的起點，在它的不是“入少出多”的后繼中選出一個點j，若j是“出少入多”的點，則邊<i, j>就是符合條件的一條路徑，結束；若這樣的j都是“入出相等”的點，則考慮j的后代：j的后繼可能都是“入少出多”的，但j的后代中必然存在至少一個點j'不是“入少出多”的（否則j的所有后代也將構成全都是“入少出多”的閉合子圖），這些j'中必然存在一個點的前趨i'是“入少出多”的，這是，需要舍棄原來的路徑，將i'作為新路徑的起點，j'作為新路徑的第一個中間點，繼續找；若j的后繼不全是“入少出多”的，則若其中有“出少入多”的則路徑已找到，若都是“入出相等”的，由于圖中無環，將路徑不斷延伸，最終一定會找到合法路徑。

由此可得，對于任何有向無環圖，這樣的路徑都是存在的，也就證明了一開始的求最小邊路徑覆蓋值的定理。
求有向無環圖最小邊路徑覆蓋值的時間復雜度：O(M+N)。