Mato is No.1

搞完了網絡流圖，搞完了一般圖，最后應該是二分圖了（在本沙茶知道的圖的范圍內）
二分圖的邊有些特別，邊<a, b>并不是表示從a到b的邊，而是從X方點a（簡記為X_a）到Y方點b（簡記為Y_b）的邊。在二分圖中，邊其實是無向的，但由于大多數引用的時候都是X方點引用Y方點，所以可以把邊看成有向的（如果實在要逆向引用的話，加一條逆向邊吧囧……）
邊類型定義（和一般圖完全一致。這里是不帶權的，如果像KM算法里面有帶權邊，加一個len域即可）：
關鍵是在初始化表頭的時候，設圖中有NX個X方點和NY個Y方點，則單點鏈表數其實只有NX。故只需弄NX個表頭即可：
然后是加邊，和一般圖完全一致：
差不多就搞完了。下面是用Dancing Link邊表實現的Hungary算法的深度優先遍歷部分：
這里xz[y]指的是y所匹配的X方點編號（若y是未蓋點則xz[y]=-1），vst[x]是X方點x是否被訪問的標志，在每次遍歷前，vst都要全部清零。

【應用實例】PKU1087
題意很難懂，其實就是：房間里有N個插座，每個插座都有一個型號（沒有兩個插座的型號相同），現在要把M個用電器插到這N個插座里，每個用電器有一個默認型號，表示該用電器只能插到其默認型號的插座里（有可能有的用電器的默認型號不與房間里的任意一個插座對應，如樣例中的X型號）。有K種適配器（每種適配器可以用無限次），每一種適配器都有兩個參數S1和S2，表示該種適配器使用一次可以將某個默認型號為S1的用電器的默認型號改為S2（同一個用電器可以被多次改變默認型號）。問在使用了若干次適配器后，最少有多少個用電器插不到插座里？
首先將每種型號作為一個點，若某種適配器的兩個參數分別為S1和S2則連邊<S1, S2>，對這個有向圖求傳遞閉包。然后再建一個二分圖，X方點表示用電器，Y方點表示插座，若X_i的初始默認型號在一開始建的有向圖中可以到達Y_j的型號（用傳遞閉包直接得到），則連邊(X_i, Y_j)。對這個二分圖求最大匹配，則(M - 最大匹配值)就是結果。
代碼：
有關圖的Dancing Link邊表的內容就到此為止了。這真是一種有大用的數據結構。

之前本沙茶成功地在網絡流圖中搞出Dancing Link邊表，那么對于一般的圖，是否也能用Dancing Link邊表呢？答案是肯定的。

邊類型（帶權的，不帶邊權的圖把len域去掉即可）： 初始化表頭：
加邊（這里是加有向邊，如果加無向邊的話，再加一條邊<b, a, len>即可）：
在一般的圖中應用Dancing Link邊表的優勢：【1】能夠有效處理刪邊刪點問題；【2】在無向圖中，能夠很快找到一條邊對應的逆向邊；【3】最大的優勢是：如果要從某一條單點鏈表（其實整個邊表可以看成N個單點鏈表的并，N為圖中的點數）的中間開始遍歷，或者逆向遍歷整個表的話，一般的鄰接鏈表幾乎不可能完成，一般的邊表也很麻煩，這種Dancing Link邊表則可以很快搞定。不過它也有缺點：空間消耗比鄰接鏈表和一般邊表大一些（不過這個影響不大）。

【應用實例】PKU1062（PKU上少有的中文題）
很水的最短路問題。將每個物品當成一個點，若j可作為i的優惠品則連邊<i, j>，邊權為優惠價格，然后，枚舉等級限制（由于物品1是必須選的，因此設最大等級限制為lmt，物品1的等級為V，則可在[V-lmt, V]范圍內枚舉最低等級，最高等級就是(最低等級+lmt)），將所有不在等級限制內的點全部刪除（其實不用真刪除，只要設一個del數組避開它們即可），求從結點1到各結點的最短路，則min(dist[i]+cs[i])（dist[i]表示1到i的最短路，cs[i]表示直接購買物品i的價格）就是結果。
代碼（2Y，一開始把solve里的g[j]弄成g[i]了囧……靜態查錯V5啊……神犇不要鄙視）：

考慮這樣一種網絡流問題：需要對同一個圖求多次最大流。則在每次求最大流之前，需要將所有邊的容量全部恢復到初始值（求最大流的過程中，邊的容量f值被改變了）。不過這還不算最猥瑣的，有的時候，我們需要在每次求最大流之前都刪去圖中的一些點或一些邊，或者改變某些原有的邊的容量，特別是需要刪點或刪邊的情況爆難搞。因為，一般的邊表中邊類型定義如下：
表示這條邊起點為a，終點為b，容量為f，鄰接邊（就是下一條起點為a的邊）的編號為next。
如果要求多次最大流，那么在每次求最大流之前就要把所有邊的容量恢復到初始值，解決方法是引入一個“初始容量”域fs，在這條邊剛剛被加入的時候將它的fs值和f值都設為初始給它的容量，在恢復時，只要將所有邊的f值恢復到fs即可。若要改變邊容量，則將該邊的fs值和f值都設為改變后的容量即可。

下面來分析需要刪邊或刪點的情況。在這種情況下，如果采用只有next的單向鏈表，則刪除時next域極難處理，而且，在一般的邊表中，還設立了表頭hd，hd[a]表示邊表中起點為a的第一條邊的編號。因此，若刪除的邊<a, b, f>是起點為a的第一條邊，還會影響hd[a]的值，使情況變得更為復雜。因此，必須采用雙向鏈表！還記得Dancing Link么？邊表其實也可以搞成Dancing Link，方法如下：
設圖中有N個點，M條邊（注意，這M條邊只包括正向邊，不包括反向邊。由于每條正向邊<a, b, f>都對應一條反向邊<b, a, 0>，因此邊表中邊的數目其實是M+M）。首先把邊表ed的0~N這(N+1)個位置（下標）空出來，作表頭（表頭不是邊，因此在遍歷邊的時候不會遍歷到它們）。其中，ed[0]為總表頭，用于遍歷ed[1..N]中每個未被刪去的點；ed[1..N]為單點表頭，ed[i]用來遍歷圖中所有以i為起點的邊（和DLX中的二維DL驚人相似）。然后，若N為偶數，則空一個位置（也就是將ed[N+1]丟棄不用），這是因為我們在增廣過程中需要引用到一條邊對應的逆向邊（正向邊對應反向邊，反向邊對應正向邊），一般認為編號為p的邊對應的逆向邊是p ^ 1，這樣，就要求圖中所有正向邊的編號都是偶數，所有反向邊的編號都是奇數（否則會造成混亂）。因此當N為偶數時，(N+1)為奇數，不能放置第一條正向邊，需要從ed[N+2]開始放置正向邊。若N為奇數則不用空位。
接下來就是邊類型了。在這里，邊類型一共需要包括6個域：a, b, fs, f, pre, next，表示這條邊起點為a，終點為b，初始容量為fs，當前容量為f，上一條起點為a的邊編號為pre，下一條起點為a的邊編號為next。注意，和DL一樣，整個鏈表是循環的，也就是我們認為表中最后一條起點為a的邊的下一條鄰接邊編號就是a（表頭），同樣，a的上一條鄰接邊也就是這條邊。
接下來就是幾個重要過程了。
（1）初始化表頭：
這里n是圖中的點數（相當于N），m是邊的編號指針（相當于DLX中的nodes）
（2）添加新邊：
這個和DLX類似，不解釋了囧……

最后進入最核心的部分——到底如何處理刪邊或刪點？有了DL型邊表就爆好搞了：刪去一條邊，只要直接刪去該邊在DL中的位置即可：
恢復一條已刪去的邊：
需要刪點的情況類似，對單點表頭處理即可。

【具體題目】PKU1815
這題就是求有向圖的字典序最小的最小點割集問題，方法是先求出最小點連通度（有關最小點連通度的求法見圖的連通度問題的求法），然后按編號遞增順序枚舉每個點，若刪去該點（其實是刪去建成的新圖中該點i'到該點附加點i''之間的邊）后圖的最小點連通度減小，則應刪去該點，否則不應刪去該點。刪去后，繼續枚舉下一個點，直到求出點割集為止。
注意，本題只有刪邊，沒有刪點，因此總表頭可以不需要，直接從ed[0]開始作單點表頭。此時，關于是否空位就剛好反過來了：如果N是奇數就要空位，N是偶數不空位（不過這題里由于建出的網絡流圖中有2*N0個結點，總是偶數，可以不管，不過本沙茶還是管這個了）。

代碼（神犇不要鄙視）：

【問題描述】
給出一個圖G和指定的源點s、匯點t，求圖中從點s到點t的第K短路。
【具體題目】PKU2449（注意：本題有一個猥瑣之處：不允許空路徑。也就是當s等于t時要將K值加1）
【算法】
本題有一種最樸素的辦法：改造Dijkstra，一開始路徑(s, 0)（這里設路徑(i, l)表示從s到i的一條長度為l的路徑）入隊。然后，每次取隊中長度最短的路徑，該路徑(i, l)出隊，可以證明，若這是終點為i的路徑第x次出隊，該路徑一定是圖中從s到i的第x短路（若x>K則該路徑已無用，舍棄）。然后從點i擴展，將擴展到的路徑全部入隊。這樣直到終點為t的路徑第K次出隊即可。
該算法容易實現（借助priority_queue），但時間復雜度可能達到O(MK)，需要優化。
優化：容易發現該算法其實有A*的思想，或者說，該算法其實是所有結點的估價函數h()值均為0的A*算法。為了優化此題，需要將h()值改大。顯然，h(i)值可以設為從i到t的最短路徑長度（容易證明它是一致的），然后g(i)=目前結點代表的路徑長度，f(i)=g(i)+h(i)，然后A*即可。

注意：更改路徑條數應該在出隊時更改，而不能在入隊時更改，因為可能在該路徑出隊之前會有新的比它更短的路徑入隊。

代碼（PKU2449）：

     摘要: 動態區間最大子序和問題【問題描述】給出一個序列A[0..N-1]和M個操作，每個操作都是以下三種之一：①：查詢區間最大子序和操作格式：1 l r表示：查詢A[l..r]內的最大子序和（就是A[l..r]內的和最大的連續子序列的和），0<=l<=r<N；②：修改單個值操作格式：2 i x表示：將A[i]的值改為x，0<=i<N；③：修改整段值操作格式：3 l ...  閱讀全文

【問題描述】
給出一個環形的字符串S，長度為N，現在要找到一個斷開點，使得從這里斷開后的字符串字典序最小。或者說，對于長度為N的字符串S[0..N-1]，找到一個位置i，使得字符串S' = S[i..N-1] + S[0..i-1]的字典序最小。若存在多個這樣的最優斷點，則取最左邊(i最小)的那個。
【Sample Input】
amandamanda
【Sample Output】
10
（從第10位斷開后得到的字符串"aamandamand"的字典序是11個斷開位置中最小的）

【分析】
首先將這個環形串拆開：只需將S[0..N-1]的后面再接上S[0..N-2]即可（如對于樣例，可構造字符串T = "amandamandaamandamand"），則T的任意一個長度為N的子串T[i..i-N+1]就是S從第i位斷開得到的字符串。此時問題就變成了：給出一個長度為(2N-1)的字符串，求出其所有長度為N的子串中字典序最小的。

設F[x]為T中所有起始位小于N的長度為x的子串中字典序最小的子串的起始位（若有多個則取最左邊的），如對于T="abaabaaababaabaaa"，有F[0]=F[1]=0，F[2]=2，F[3]=F[4]=5……本題的目的就是求出F[N]的值。一開始已知的只有F[0]=0（長度為0的字符串都是空串，字典序都是最小的，取最左邊的第0位）。

可以發現，F數組有很多重要的性質：
性質1 F[0..N]數組是單調遞增的。
證明：用反證法。設存在一個值x(0<=x<N)使得F[x]>F[x+1]則根據定義，有T[F[x+1]..F[x+1]+x]<=T[F[x]..F[x]+x]（這里一定不會越界，即F[x]+x的值一定不大于(2N-1)，因為x<N，又根據得F[x]<N，故F[x]+x<2N），這樣，必有T[F[x+1]..F[x+1]+x-1]<=T[F[x]..F[x]+x-1]。然而根據F[x]的定義又可以得到T[F[x+1]..F[x+1]+x-1]>T[F[x]..F[x]+x-1]（否則F[x]的值就應該等于F[x+1]的值了），矛盾，故在F[0..N]中不可能存在任何F[x]>F[x+1]的情況，也即F[0..N]數組是單調遞增的（以下將F[0..N]數組簡稱為F數組）。
性質2 對于任意值x(0<=x<N)，必然滿足F[x+1]=F[x]或F[x+1]>F[x]+x。
證明：因為前面已經證明了F數組是單調遞增的，這里只需證明對于任意x(0<=x<N)，不存F[x]<F[x+1]<=F[x]+x的情況即可。
這里同樣用反證法。設存在一個值x(0<=x<N)使得F[x]<F[x+1]<=F[x]+x。則根據定義有T[F[x+1]..F[x+1]+x]<T[F[x]..F[x]+x]且T[F[x]..F[x]+x-1]<=T[F[x+1]..F[x+1]+x-1]，這樣必有T[F[x]..F[x]+x-1]=T[F[x+1]..F[x+1]+x-1]且T[F[x+1]+x]<T[F[x]+x]。設D=F[x+1]-F[x]，則T[F[x]]=T[F[x]+D]，因為D<=x，可得T[F[x]+D]=T[F[x]+2D]，即T[F[x]]=T[F[x]+2D]。這樣，T[F[x]..F[x]+x-D-1]=T[F[x]+2D..F[x]+x+D-1]；又因為T[F[x]+x-D]=T[F[x]+x]，而T[F[x+1]+x]（即T[F[x]+x+D]]）<T[F[x]+x]，這樣，T[F[x]+x+D]<T[F[x]+x-D]，也就是，T[F[x]+2D..F[x]+x+D]<T[F[x]..F[x]+x-D]！這樣可以得出，從(F[x]+2D)位開始的任意長度不小于(x-D)的子串，其字典序都小于從F[x]位開始的同樣長度的子串，由于F[x]<F[x+1]<=F[x]+x，D=F[x+1]-F[x]，所以有1<=D<=x，這樣，F[x]的值就應該是(F[x]+2D)了，這顯然不可能。所以，一開始假設的這種情況是不可能存在的，即對于任意值x（0<=x<N），必然滿足F[x+1]=F[x]或F[x+1]>F[x]+x。

根據F數組的以上兩個性質可以設計出本題的算法：
設目前已經求出了F[0..x-1]的值，且F[x-1]=i。首先將T[0..i-1]全部刪去（因為F數組是單調遞增的，F[x]的值一定不小于i），然后對T自身作擴展KMP（就是以T為模板串，T為子串的擴展KMP，相當于其預處理部分），一開始先將F[x]置為i，設第j位的匹配長度為next[j]，若next[j]=x-1且T[j+x-1]<T[i+x-1]，則將F[x]的值改為j，這樣掃描一遍，即求出了F[x]的值。若掃描過程中未出現任何next[j]=x-1，則設所有next[j]值不小于x的最小next[j]值為y，則可以直接得到F[x..y-1]的值均等于F[x-1]。就這樣直到求出F[N]的值為止。

時間復雜度：O(NÖN)，可以根據性質2得到。

KMP：給出兩個字符串A（稱為模板串）和B（稱為子串），長度分別為lenA和lenB，要求在線性時間內，對于每個A[i]（0<=i<lenA)，求出A[i]往前和B的前綴匹配的最大匹配長度，記為ex[i]（或者說，ex[i]為滿足A[i-z+1..i]==B[0..z-1]的最大的z值）。KMP的主要目的是求B是不是A的子串，以及若是，B在A中所有出現的位置（當ex[i]=lenB時）。
【算法】
設next[i]為滿足B[i-z+1..i]==B[0..z-1]的最大的z值（也就是B的自身匹配）。設目前next[0..lenB-1]與ex[0..i-1]均已求出，要用它們來求ex[i]的值。
根據ex的定義，有A[i-1-ex[i-1]+1..i-1]==B[0..ex[i-1]-1]，這時，若有A[i]==B[ex[i-1]]，則可以直接得到ex[i]=ex[i-1]+1（因為i-1-ex[i-1]+1即i-ex[i-1]，現在由于A[i]==B[ex[i-1]]，可得A[i-ex[i-1]..i]==B[0..ex[i-1]]，即A[i-ex[i-1]+1-1..i]==B[0..ex[i-1]+1-1]，所以ex[i]=ex[i-1]+1）。若A[i]!=B[ex[i-1]]？
設j=next[ex[i-1]-1]，則根據next定義得B[ex[i-1]-j..ex[i-1]-1]==B[0..j-1]，又因為A[i-ex[i-1]..i-1]==B[0..ex[i-1]-1]得A[i-j..i-1]==B[ex[i-1]-j..ex[i-1]-1]，這樣有A[i-j..i-1]==B[0..j-1]！也就是此時只需再比較A[i]與B[j]的值是否相等即可，若相等，可得ex[i]=j+1，若仍不相等，則更新j為next[j-1]，繼續比較A[i]與B[j]是否相等……直到A[i]與B[j]相等或直到j==0時，A[i]仍不等于B[j]，此時ex[i]=0。邊界：求ex[0]時，初始j（用來代替ex[i-1]）為0。
現在還有一個問題，如何求next？顯然next就是以B自身為模板串，B為子串的“自身匹配”，用類似的辦法即可，唯一不同的是next[0]=lenB可以直接得到，求next[1]時，初始j（代替next[i-1]）為0。
【核心代碼】
擴展KMP：給出模板串A和子串B，長度分別為lenA和lenB，要求在線性時間內，對于每個A[i]（0<=i<lenA)，求出A[i..lenA-1]與B的最長公共前綴長度，記為ex[i]（或者說，ex[i]為滿足A[i..i+z-1]==B[0..z-1]的最大的z值）。擴展KMP可以用來解決很多字符串問題，如求一個字符串的最長回文子串和最長重復子串。
【算法】
設next[i]為滿足B[i..i+z-1]==B[0..z-1]的最大的z值（也就是B的自身匹配）。設目前next[0..lenB-1]與ex[0..i-1]均已求出，要用它們來求ex[i]的值。
設p為目前A串中匹配到的最遠位置，k為讓其匹配到最遠位置的值（或者說，k是在0<=i0<i的所有i0值中，使i0+ex[i0]-1的值最大的一個，p為這個最大值，即k+ex[k]-1），顯然，p之后的所有位都是未知的，也就是目前還無法知道A[p+1..lenA-1]中的任何一位和B的任何一位是否相等。
根據ex的定義可得，A[k..p]==B[0..p-k]，因為i>k，所以又有A[i..p]==B[i-k..p-k]，設L=next[i-k]，則根據next的定義有B[0..L-1]==B[i-k..i-k+L-1]。考慮i-k+L-1與p-k的關系：
（1）i-k+L-1<p-k，即i+L<=p。這時，由A[i..p]==B[i-k..p-k]可以得到A[i..i+L-1]==B[i-k..i-k+L-1]，又因為B[0..L-1]==B[i-k..i-k+L-1]所以A[i..i+L-1]==B[0..L-1]，這就說明ex[i]>=L。又由于next的定義可得，A[i+L]必然不等于B[L]（否則A[i..i+L]==B[0..L]，因為i+L<=p，所以A[i..i+L]==B[i-k..i-k+L]，這樣B[0..L]==B[i-k..i-k+L]，故next[i-k]的值應為L+1或更大），這樣，可以直接得到ex[i]=L！
（2）i+k-L+1>=p-k，即i+L>p。這時，首先可以知道A[i..p]和B[0..p-i]是相等的（因為A[i..p]==B[i-k..p-k]，而i+k-L+1>=p-k，由B[0..L-1]==B[i-k..i-k+L-1]可得B[0..p-i]==B[i-k..p-k]，即A[i..p]==B[0..p-i]），然后，對于A[p+1]和B[p-i+1]是否相等，目前是不知道的（因為前面已經說過，p是目前A串中匹配到的最遠位置，在p之后無法知道任何一位的匹配信息），因此，要從A[p+1]與B[p-i+1]開始往后繼續匹配（設j為目前B的匹配位置的下標，一開始j=p-i+1，每次比較A[i+j]與B[j]是否相等，直到不相等或者越界為止，此時的j值就是ex[i]的值）。在這種情況下，p的值必然會得到延伸，因此更新k和p的值。
邊界：ex[0]的值需要預先求出，然后將初始的k設為0，p設為ex[0]-1。
對于求next數組，也是“自身匹配”，類似KMP的方法處理即可。唯一的不同點也在邊界上：可以直接知道next[0]=lenB，next[1]的值預先求出，然后初始k=1，p=ex[1]。

需要嚴重注意的是，在上述的情況（2）中，本該從A[p+1]與B[p-i+1]開始匹配，但是，若p+1<i，也就是p-i+1<0（這種情況是有可能發生的，當ex[i-1]=0，且前面的ex值都沒有延伸到i及以后的時候）的話，需要將A、B的下標都加1（因為此時p必然等于i-2，如果A、B的下標用兩個變量x、y控制的話，x和y都要加1）！！

【核心代碼】
【時間復雜度分析】
在KMP和擴展KMP中，不管是A串還是B串，其匹配位置都是單調遞增的，故總時間復雜度是線性的，都為O(lenA + lenB)（只是擴展KMP比KMP的常數更大一些）。
【應用】
KMP和擴展KMP在解決字符串問題中有大用。很多看上去很猥瑣的字符串問題，都可以歸結到這兩種算法之中。另外，這里的“字符串”可以延伸為一切類型的數組，而不僅僅是字符數組。

放了快2個月了……（準確來說放了2年了，本沙茶從2年前就開始捉這道猥瑣題……）
DLX重復覆蓋的幾點說明：
（1）必須有啟發函數優化，否則TLE；
（2）不需要二分下界，只要將目前f值（f=g+h，即實際深度加上啟發函數值）與目前求得的最優解比較即可，f>=最優解即剪枝；
（3）刪一整列（delcol）操作時，可以從任意一個結點開始刪（不一定要向精確覆蓋那樣非要從列頭開始），但是，開始的那個結點不刪！恢復（resucol）時也不恢復開始的那個結點！這是為了在接下來的橫向遍歷中不受影響。由于不刪開始結點，所以在將最優列刪除時，需要循環一次刪除一次，恢復一次。

代碼：（RQNOJ P89）

總結：DLX精確覆蓋和重復覆蓋其實是有大用的，很多搜索問題都可以轉化為這兩種問題，效率奇高無比，且寫起來也很容易（只是在建模的時候可能有點猥瑣，下面的模板，和網絡流一樣，10min的事），至于NOIP2009引出的數獨系列問題，精確覆蓋可以直接秒殺。

圖的連通度問題是指：在圖中刪去部分元素（點或邊），使得圖中指定的兩個點s和t不連通（不存在從s到t的路徑），求至少要刪去幾個元素。
圖的連通度分為點連通度和邊連通度：
（1）點連通度：只許刪點，求至少要刪掉幾個點（當然，s和t不能刪去，這里保證原圖中至少有三個點）；
（2）邊連通度：只許刪邊，求至少要刪掉幾條邊。
并且，有向圖和無向圖的連通度求法不同，因此還要分開考慮（對于混合圖，只需將其中所有的無向邊按照無向圖的辦法處理、有向邊按照有向圖的辦法處理即可）。

【1】有向圖的邊連通度：
這個其實就是最小割問題。以s為源點，t為匯點建立網絡，原圖中的每條邊在網絡中仍存在，容量為1，求該網絡的最小割（也就是最大流）的值即為原圖的邊連通度。

【2】有向圖的點連通度：
需要拆點。建立一個網絡，原圖中的每個點i在網絡中拆成i'與i''，有一條邊<i', i''>，容量為1（<s', s''>和<t', t''>例外，容量為正無窮）。原圖中的每條邊<i, j>在網絡中為邊<i'', j'>，容量為正無窮。以s'為源點、t''為匯點求最大流，最大流的值即為原圖的點連通度。

說明：最大流對應的是最小割。顯然，容量為正無窮的邊不可能通過最小割，也就是原圖中的邊和s、t兩個點不能刪去；若邊<i, i''>通過最小割，則表示將原圖中的點i刪去。

【3】無向圖的邊連通度：
將圖中的每條邊(i, j)拆成<i, j>和<j, i>兩條邊，再按照有向圖的辦法（【1】）處理；

【4】無向圖的點連通度：
將圖中的每條邊(i, j)拆成<i, j>和<j, i>兩條邊，再按照有向圖的辦法（【2】）處理。

有向無環圖的最小路徑覆蓋問題包括兩種（設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)。