Mato is No.1

有向無(wú)環(huán)圖的最小路徑覆蓋問(wèn)題包括兩種（設(shè)G是一個(gè)有向無(wú)環(huán)圖，S是G的一個(gè)路徑集合）：
（1）最小點(diǎn)路徑覆蓋：滿(mǎn)足對(duì)于G中所有的點(diǎn)i，i在S中的一條路徑中出現(xiàn)，且只在S中的一條路徑中出現(xiàn)，求S的最小容量；
（2）最小邊路徑覆蓋：滿(mǎn)足對(duì)于G中所有的邊E，E在S中的一條路徑中出現(xiàn)，且只在S中的一條路徑中出現(xiàn)，求S的最小容量；

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

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

由此可得，對(duì)于任何有向無(wú)環(huán)圖，這樣的路徑都是存在的，也就證明了一開(kāi)始的求最小邊路徑覆蓋值的定理。
求有向無(wú)環(huán)圖最小邊路徑覆蓋值的時(shí)間復(fù)雜度：O(M+N)。