Mato is No.1

網絡流最讓人不能忍受的不是模板，而是建模！尤其是某些題目里面需要搞一段很長的預處理才能開始寫網絡流……

最大閉合子圖就是其中的一種。如果要求最大閉合子圖的有向圖里面有環就很囧了，因為在某些題目里（比如NOI2009的pvz），取點是有先后順序的，因此環中的點一個也取不了（有的題則不是這樣，子圖里的點可以一次全部取來，這時對于環就有兩種方案了：要么全取，要么一個不取，此時不用管環，直接進入網絡流即可），不僅如此，根據閉合子圖的定義，如果一個點i可以到達一個點j（注，是“可以到達”點j，也就是從i到j有路徑），而點j屬于某個環，那么點i也不能取，因此在預處理中需要把點i也刪掉。以下將屬于某個環中的點成為“環點”，將可以到達環點的點稱為“環限制點”，這兩種點在預處理中都要刪除。

本沙茶以前用的一般方法是：先求圖的傳遞閉包，找出所有的環點（能夠到達自己的點），再從每個環點開始進行逆向遍歷（將原圖所有邊反向，再遍歷），找到所有的環限制點。該方法的時間復雜度高達O(N³)，且寫起來也爆麻煩。

其實，真正用于去環的最佳方法是拓撲排序?。?！

首先將原圖的所有邊反向，然后進行拓撲排序，所有遍歷到的點是保留下來的點，而沒有遍歷到的點就是環點或環限制點，需要刪除。
【證明：環點顯然是不可能被遍歷到的，而在反向后的新圖中，對于一個環限制點j，必然存在一個環點i能夠到達它，而i不能被遍歷到，故j也不能被遍歷到。除了這兩種點外，其它的點的所有前趨必然也都不是環點或環限制點（否則這些點就成了環限制點），因此只要入度為0（不存在前趨）的點能夠遍歷到，這些點也能夠遍歷到，而入度為0的點顯然能遍歷到，故這些點也能被遍歷到。證畢】
由于求反向圖和拓撲排序都可以在O(M)時間內完成，整個去環過程的時間復雜度就是O(M)的。

下面附上NOI2009 pvz代碼：（注意，本題的第9個點是一個超級大數據，最后建出來的網絡的邊數將會達到300000，故MAXM取150000，另外，本題必須使用Dinic，SAP會超）

【這次市選我掛得很慘……前3題全部爆0（騙分都米騙到）……就這種爛成績還能進市隊，可見合肥人之沙茶……】
最不該掛的是第一題。第一問就是個裸的最大閉合子圖，關鍵就出在第二問上，要求最大閉合子圖的最小容量。本沙茶后來才發現這竟然是PKU原題?。≒KU2987），因為，最大流求出來的最大閉合子圖一定是容量最小的！故第二問只要在求出最大流后來一次遍歷，找到S可達的結點個數即可。

詳細證明（轉網上某神犇的）：
———————————————————————————————————————————————————最大權不可能是負數，當是0的情況，自然是一個點不選最優，下面探討忽略0的情況。

         1：首先我假設有兩個閉合子圖都擁有相同的最大權，并且沒有共同點，很容易證明不會出現這種情況，因為如果我們把兩個閉合子圖都選擇上，那么最大權會變大。

         2：仍然假設有兩個閉合子圖都擁有相同的最大權，但是有共同點，即重疊的意思。根據閉合圖的特點，這些共同點不是隨意的，可以知道，只要有一個點相同，那么這個點的能到達的所有后續點都必定是共同點。所以會得出一個結論，兩個閉合子圖重疊，重疊的部分必然是1個或者多個不重疊閉合圖。


    然后我們考慮不重疊的部分，這部分的點權和可以證明一定是非負。我們可以假設非重疊部分的點權和是負數，那么假如我們刪掉這部分，只選取重疊部分（因為重疊部分肯定是閉合圖），那么最大權也會變大，矛盾。所以非重疊部分點權和一定是非負數。
    下面繼續探討非重疊部分的性質。上面的證明已經得出他們的點權和一定是非負。下面先拋開點權和等于0的情況，先討論正數的情況。
假設兩個閉合子圖的非重疊部分都是正數，那么把這兩個部分加起來重新構成閉合圖，最大權必然會變大，與假設的兩個同為最大權的閉合圖矛盾。固可以證明非重疊部分的點權和肯定是0。

    探討到這部分，我們已經可以初步得出一個結論，就是一個最大權閉合子圖的點數多少問題只能受到一些0權和子圖（所有點權加起來等于0的子圖）的干擾。

    重點來到這些0權和子圖上。下面我們又來做一個假設，就是假設我們求出了一個最大權閉合子圖，并且里面有包含到一些0權和子圖。而我們這時候需要做的就是找到那些可以刪去的0權和子圖，當我們刪去了所有的這些子圖，那么點數就可以達到最小。

    關鍵來了。到底哪些0權和子圖是可以刪去的，哪些0權和子圖是不可以刪去的呢？

    根據閉合圖的性質，我們要刪除一個點，那么必須把所有能到達這個點的點刪去。那么很清晰的看到要刪除一個子圖，必須保證在這個子圖外沒有任何一個點指向這個子圖。也就是說這個子圖是封閉的，只有出邊，沒有入邊。



    最后一步，假如我們能證明在求解最大權閉合圖的過程中保證不會選上這些0權和子圖，那么這個證明就可以結束了。
通過最大流求解最大權閉合子圖，我們把正點權和源點建邊，邊權為點權值，負點權和匯點建邊，邊權為點權絕對值。仔細分析求解最大流的過程，會發現一些東西。

    由于那些可選可不選的0權和子圖是封閉的，沒有入邊的，那么在求解最大流的過程中，不可能有外部流補充，所以這些0權和子圖的每個點與源或者匯的邊都是滿流的。





    最后求最大權閉合子圖的點，方法是從源點開始通過非滿流邊搜索一個聯通圖，圖內的點（除了源點）就是求出來的最大權閉合子圖的點。而上面證明到0權和子圖的點和源匯都是滿流，并且沒有入邊，出邊也沒有流，那么肯定無法從源點搜索到。那么在求解的過程中這些0權和子圖的點是肯定沒有選上的。

   就此證畢。
   結論：通過最大流求解最大權閉合子圖的問題，求出來的閉合子圖點數也是最少的。

———————————————————————————————————————————————————
代碼：

歐拉環：圖中經過每條邊一次且僅一次的環；
歐拉路徑：圖中經過每條邊一次且僅一次的路徑；
歐拉圖：有至少一個歐拉環的圖；
半歐拉圖：沒有歐拉環，但有至少一條歐拉路徑的圖。

【無向圖】
一個無向圖是歐拉圖當且僅當該圖是連通的（注意，不考慮圖中度為0的點，因為它們的存在對于圖中是否存在歐拉環、歐拉路徑沒有影響）且所有點的度數都是偶數；一個無向圖是半歐拉圖當且僅當該圖是連通的且有且只有2個點的度數是奇數（此時這兩個點只能作為歐拉路徑的起點和終點）；

證明：因為任意一個點，歐拉環（或歐拉路徑）從它這里進去多少次就要出來多少次，故(進去的次數+出來的次數)為偶數，又因為(進去的次數+出來的次數)=該點的度數（根據定義），所以該點的度數為偶數。

【有向圖】
一個有向圖是歐拉圖當且僅當該圖的基圖（將所有有向邊變為無向邊后形成的無向圖，這里同樣不考慮度數為0的點）是連通的且所有點的入度等于出度；一個有向圖是半歐拉圖當且僅當該圖的基圖是連通的且有且只有一個點的入度比出度少1（作為歐拉路徑的起點），有且只有一個點的入度比出度多1（作為終點），其余點的入度等于出度。

證明：與無向圖證明類似，一個點進去多少次就要出來多少次。

【無向圖、有向圖中歐拉環的求法】
與二分圖匹配算法類似，是一個深度優先遍歷的過程，時間復雜度O(M)（因為一條邊最多被訪問一次）。核心代碼（邊是用邊表存儲的而不是鄰接鏈表，因為無向圖中需要對其逆向的邊進行處理，在有向圖中，可以用鄰接鏈表存儲邊）：
要注意的是在res中寫入是逆序的，所以初始的v應設成(邊數-1)。
但是有一個問題是，這是遞歸實現的，當點數過多時有爆棧危險，所以最好使用非遞歸：
當原圖是歐拉圖時，一定可以求出歐拉回路。當原圖是半歐拉圖時，求歐拉路徑，只要找到起點i和終點j，添加邊<j, i>（或(j, i)），求歐拉環，再在求出的歐拉環中刪除添加的新邊即可。

不過最為BT的還不是這個，而是接下來的——
【混合圖】
混合圖（既有有向邊又有無向邊的圖）中歐拉環、歐拉路徑的判定需要借助網絡流！

（1）歐拉環的判定：
一開始當然是判斷原圖的基圖是否連通，若不連通則一定不存在歐拉環或歐拉路徑（不考慮度數為0的點）。

其實，難點在于圖中的無向邊，需要對所有的無向邊定向（指定一個方向，使之變為有向邊），使整個圖變成一個有向歐拉圖（或有向半歐拉圖）。若存在一個定向滿足此條件，則原圖是歐拉圖（或半歐拉圖）否則不是。關鍵就是如何定向？

首先給原圖中的每條無向邊隨便指定一個方向（稱為初始定向），將原圖改為有向圖G'，然后的任務就是改變G'中某些邊的方向（當然是無向邊轉化來的，原混合圖中的有向邊不能動）使其滿足每個點的入度等于出度。
設D[i]為G'中(點i的出度 - 點i的入度）。可以發現，在改變G'中邊的方向的過程中，任何點的D值的奇偶性都不會發生改變（設將邊<i, j>改為<j, i>，則i入度加1出度減1，j入度減1出度加1，兩者之差加2或減2，奇偶性不變）！而最終要求的是每個點的入度等于出度，即每個點的D值都為0，是偶數，故可得：若初始定向得到的G'中任意一個點的D值是奇數，那么原圖中一定不存在歐拉環！

若初始D值都是偶數，則將G'改裝成網絡：設立源點S和匯點T，對于每個D[i]>0的點i，連邊<S, i>，容量為D[i]/2；對于每個D[j]<0的點j，連邊<j, T>，容量為-D[j]/2；G'中的每條邊在網絡中仍保留，容量為1（表示該邊最多只能被改變方向一次）。求這個網絡的最大流，若S引出的所有邊均滿流，則原混合圖是歐拉圖，將網絡中所有流量為1的中間邊（就是不與S或T關聯的邊）在G'中改變方向，形成的新圖G''一定是有向歐拉圖；若S引出的邊中有的沒有滿流，則原混合圖不是歐拉圖。

為什么能這樣建圖？
考慮網絡中的一條增廣路徑S-->i-->...-->j-->T，將這條從i到j的路徑在G'中全部反向，則：i的入度加1出度減1，j的入度減1出度加1，路徑中其它點的入度出度均不變。而i是和S相連的，因此初始D[i]>0，即i的出度大于入度，故這樣反向之后D[i]減少2；同理，j是和T相連的，這樣反向之后D[j]增加2。因此，若最大流中邊<S, i>滿流（流量為初始D[i]/2），此時D[i]值就變成了0，也就是i的入度等于出度。因此只要使所有S引出的邊全部滿流，所有初始D值>0的點的D值將等于0，又因為將邊變向后所有點的D值之和不變，所有初始D值小于0的點的D值也將等于0，而初始D值等于0的D點既不與S相連也不與T相連，所以它們是網絡中的中間點，而中間點的流入量等于流出量，故它們的入度和出度一直不變，即D值一直為0。因此，整個圖G'成為歐拉圖。

（2）歐拉路徑的判定：
首先可以想到的是枚舉歐拉路徑的起點i和終點j，然后在圖中添加邊<j, i>，再求圖中是否有歐拉回路即可。但是，該算法的時間復雜度達到了O(M * 最大流的時間)，需要優化。
前面已經說過，在將邊變向的過程中任何點的D值的奇偶性都不會改變，而一個有向圖有歐拉路徑的充要條件是基圖連通且有且只有一個點的入度比出度少1（作為歐拉路徑的起點），有且只有一個點的入度比出度多1（作為終點），其余點的入度等于出度。這就說明，先把圖中的無向邊隨便定向，然后求每個點的D值，若有且只有兩個點的初始D值為奇數，其余的點初始D值都為偶數，則有可能存在歐拉路徑（否則不可能存在）。進一步，檢查這兩個初始D值為奇數的點，設為點i和點j，若有D[i]>0且D[j]<0，則i作起點j作終點（否則若D[i]與D[j]同號則不存在歐拉路徑），連邊<j, i>，求是否存在歐拉環即可（將求出的歐拉環中刪去邊<j, i>即可）。這樣只需求一次最大流。

【典型例題】Sightseeing tour（PKU1637，ZJU1992）
本題就是求混合圖的歐拉環問題，題目中已經說明圖是連通的（Input的最后一句話），故不需判連通。
（本沙茶一開始把DFS中的l0 = aug中的"= aug"寫漏了，TLE了N次）

在二分圖最大匹配中，每個點（不管是X方點還是Y方點）最多只能和一條匹配邊相關聯，然而，我們經常遇到這種問題，即二分圖匹配中一個點可以和多條匹配邊相關聯，但有上限，或者說，L_i表示點i最多可以和多少條匹配邊相關聯。

二分圖多重匹配分為二分圖多重最大匹配與二分圖多重最優匹配兩種，分別可以用最大流與最大費用最大流解決。

（1）二分圖多重最大匹配：
在原圖上建立源點S和匯點T，S向每個X方點連一條容量為該X方點L值的邊，每個Y方點向T連一條容量為該Y方點L值的邊，原來二分圖中各邊在新的網絡中仍存在，容量為1（若該邊可以使用多次則容量大于1），求該網絡的最大流，就是該二分圖多重最大匹配的值。

（2）二分圖多重最優匹配：
在原圖上建立源點S和匯點T，S向每個X方點連一條容量為該X方點L值、費用為0的邊，每個Y方點向T連一條容量為該Y方點L值、費用為0的邊，原來二分圖中各邊在新的網絡中仍存在，容量為1（若該邊可以使用多次則容量大于1），費用為該邊的權值。求該網絡的最大費用最大流，就是該二分圖多重最優匹配的值。

例題：
【1】POJ1698 Alice's Chance
將電影作為X方點，每一天作為Y方點（最多50周，每周7天，所以共設350個Y方點），若第i個電影可以在第j天搞就連邊(i, j)。每個X方點的L值為該電影總共要搞多少天，每個Y方點的L值為1（每天最多只能搞一個電影），然后求二分圖多重最大匹配，若能使所有從源點連向X方點的邊都滿流，則輸出Yes，否則輸出No。
【2】POJ2112 Optimal Milking
先預處理求出每兩個點（包括擠奶點和牛）間的最短距離，然后將所有擠奶點作為X方點（L值為該擠奶點最多可以容納多少牛），所有牛作為Y方點（L值為1），X_i和Y_j間邊的權值為這兩個點之間的最短距離（若這兩點間不存在路徑則此處無邊），然后問題就變成了求一個多重匹配，使得每個Y方點都有匹配點且匹配邊中權值的最大值最小。
可以枚舉最大邊權值S，然后，原圖中所有權值大于S的邊都要刪去。若此時圖中存在符合要求的多重匹配，則S合法否則S不合法。由于S的合法性是單調的，所以可以二分枚舉S。

今天終于搞懂了RMQ問題無比神犇的ST算法……

【離線RMQ問題】
題意：對于一個序列A[1..N]，共有M次提問，每次都是問A[l..r]（1<=l<=r<=N)中的最值，求出每次提問的答案。

（1）純暴力枚舉：O(NM)；
（2）樹狀數組：O(M(logN)^2)【見樹狀數組解決離線RMQ問題】
（3）ST算法：O(MlogN)……
ST算法是基于分塊DP的。
設F[i][j]為A[i..(i+2^j-1)]（共2^j個元素）中的最值（前提是不能越界，即i+2^j-1 <= N），顯然F可以通過DP的方式得到：
F[i][j] = min||max{F[i][j-1], F[i+2^(j-1)][j-1]}
邊界：F[i][0]=A[i]。
DP求F的值的時間復雜度為O(NlogN)（一共只有NlogN個F值有意義）；

然后，對于求A[l..r]中的最值，只要將A[l..r]拆成若干連續的段，使得每段的長度都是2的整數次冪就行了，比如A[3..28]可以拆成A[3..18]、A[19..26]、A[27..28]三段，長度分別是16（2^4）、8（2^3）、2（2^1），所以min||max{A[3..28]} = min||max{F[3][4], F[19][3], F[27][1]}。
關鍵是怎么拆？方法：求出(r-l+1)（即A[l..r]的長度）的二進制形式，然后從高位到低位依次遍歷，如果找到1位就加上目前的位對應的冪，如(28-3+1)=(11010)2，所以依次找到F[3][4]、F[3+2^4][3]、F[3+2^4+2^3][1]。注意此時需要預先設一個數組B，B[2^i]=i，以方便找到某個取出的冪對應的指數。
顯然，最多只有logN段，所以一次提問的時間復雜度為O(logN)。

其實還有一種方法，就是先求出log(r-l+1)的值（下取整），設為x，然后F[l][x]和F[r-2^x+1][x]中的較大/較小值就是A[l..r]中的最值。這樣，一次提問的時間復雜度就降到了O(1)。問題是，系統log函數灰常慢，也許算一次log函數值的時間已經超過了logN，這樣顯然得不償失。所以仍然推薦上面的方法。

【核心代碼（以求最小值為例，最大值類似）】
分段法：
求log值法：
求F數組值的預處理代碼（注意，如果采用求log值的方法就不需要B數組了）：

【后經效率測試，發現當N=M=100000的隨機數據中，兩種方法都可以在0.4s以內得出正確結果，其中log值法比分段法略慢0.01s左右，相差不大，但考慮到“盡量少使用數學函數”的原則，仍推薦分段法】

依照CLJ神犇的指示，最近本沙茶決定開始被數據結構題虐……先找來了省內的一道題（就是這道囧）……

題目大意：求兩個長度為5N的序列的最長公共子序列長度，在兩個序列中，整數1~N分別都出現5次。1<=N<=20000。

【注：本沙茶一開始用線段樹的，后來在看了CLJ神犇的標程（Orz?。。┲蠼K于明白了樹狀數組解法囧……】

LCS問題的樸素時間復雜度為O(NM)。對于本題顯然需要優化。
觀察LCS的轉移方程：
F[i][j] = F[i-1][j-1]+1（當A[i]==B[j]時）
F[i][j] = max{F[i-1][j], F[i][j-1]}（當A[i]!=B[j]時）

可以將F用滾動數組來表示，即設F'為上階段的F（即F[i-1]），則本階段的F（即F[i]）可以由F'求得：
F[j] = F'[j-1]+1（當A[i]==B[j]時）
F[j] = max{F'[j], F[j-1]}（當A[i]!=B[j]時）

進一步，這個F'其實都不用記錄，只需在每一階段更新一遍F即可：
F[j] = F[j-1]+1（當A[i]==B[j]時）
F[j] = max{F[j], F[j-1]}（當A[i]!=B[j]時）
不過需要逆序更新（保證F[j-1]是上一階段的而不是本階段的），這與01背包有點像。

由題意可以發現，A[i]==B[j]的出現次數極少，在每階段中只會出現5次！我們可以預先求出這5個地方的值，然后對于其它的F[j]，其在本階段的值其實就是它前面的最大值（max{F[1..j-1]}），又因為我們最后只需知道F[N']（N'=5N，即序列長度）即可，故可設計出以下算法：
一開始F[1..N]均為0，然后將以下內容執行N'次，第i次：
（1）求出B序列中與A[i]相等的5個元素的位置，設為S[1..5]；
（2）依次更新F[S[5..1]]，每個都更新為它前面的最大值加1（很容易知道為神馬），其它的值暫時不管；

N'次執行完后，整個序列中的最大值就是F[N']的值。由于這個算法中出現的主要操作是改動一個指定位置元素的值和找一個前綴區間中的最大值，因此可以采用樹狀數組，時間復雜度O(NlogN）（線段樹必TLE）。

【總結：在本題中使用了一種“推遲更新”的方法，即需要更新一個值時，先暫時不理它，等到需要引用到它的時候再更新。這種方法最常見的應用就是線段樹的結點標記。不過要注意的是，如果該值的推遲更新會對它后面要更新的值帶來問題（也就是，這些后更新的值需要引用該值的新值），就不能使用這種方法。在本題中，其它位置的值的改變只與這5個特殊的位置有關，與其它因素無關，故可以使用這種方法?！?br>

樹狀數組與線段樹不同，它只能直接支持前綴區間（[1..r]）或后綴區間（[l..N]）上的操作，而對于一般區間（[l..r]）上的操作則需要通過兩步操作間接完成：先對[1..r]進行操作再對[1..l-1]進行反操作（如加c的反操作就是減c），對于加法操作這樣可反的操作是可以，而對于求最值這樣的不可反的操作（無法通過[1..r]的最值與[1..l-1]的最值得出[l..r]的最值），就沒有辦法了。其實，用樹狀數組是可以解決離線RMQ問題的，但時間復雜度不太理想（一次操作的理論時間復雜度達O((logN)^2)）。

方法是（這里C[i]表示i管轄的數組結點中的最值）：設r'為目前的右端點，一開始r'=r。每次找到r'管轄的數組結點中最左邊的那個的下標（即r' - (r' & (-r')) + 1），設為x。若x>=l，則將C[r']與目前的最值比較、更新，再將r'設為(x-1)；若x<l，則調出A[r']的值與目前最值比較、更新，然后將r'減1。如此直至r'<l為止。

本算法編程復雜度極低，但由于時間效率較低，難以適應較大范圍數據（N, M>100000基本上就TLE了）

樹狀數組在區間求和問題上有大用，其三種復雜度都比線段樹要低很多……有關區間求和的問題主要有以下三個模型（以下設A[1..N]為一個長為N的序列，初始值為全0）：

（1）“改點求段”型，即對于序列A有以下操作：

【1】修改操作：將A[x]的值加上c；

【2】求和操作：求此時A[l..r]的和。

這是最容易的模型，不需要任何輔助數組。樹狀數組中從x開始不斷減lowbit(x)（即x&(-x)）可以得到整個[1..x]的和，而從x開始不斷加lowbit(x)則可以得到x的所有前趨。代碼：

 

操作【1】：ADD(x, c);

操作【2】：SUM(r)-SUM(l-1)。

（2）“改段求點”型，即對于序列A有以下操作：

【1】修改操作：將A[l..r]之間的全部元素值加上c；

【2】求和操作：求此時A[x]的值。

這個模型中需要設置一個輔助數組B：B[i]表示A[1..i]到目前為止共被整體加了多少（或者可以說成，到目前為止的所有ADD(i, c)操作中c的總和）。

則可以發現，對于之前的所有ADD(x, c)操作，當且僅當x>=i時，該操作會對A[i]的值造成影響（將A[i]加上c），又由于初始A[i]=0，所以有A[i] = B[i..N]之和！而ADD(i, c)（將A[1..i]整體加上c），將B[i]加上c即可——只要對B數組進行操作就行了。

這樣就把該模型轉化成了“改點求段”型，只是有一點不同的是，SUM(x)不是求B[1..x]的和而是求B[x..N]的和，此時只需把ADD和SUM中的增減次序對調即可（模型1中是ADD加SUM減，這里是ADD減SUM加）。代碼：

操作【1】：ADD(l-1, -c); ADD(r, c);

操作【2】：SUM(x)。

（3）“改段求段”型，即對于序列A有以下操作：

【1】修改操作：將A[l..r]之間的全部元素值加上c；

【2】求和操作：求此時A[l..r]的和。

這是最復雜的模型，需要兩個輔助數組：B[i]表示A[1..i]到目前為止共被整體加了多少（和模型2中的一樣），C[i]表示A[1..i]到目前為止共被整體加了多少的總和（或者說，C[i]=B[i]*i）。

對于ADD(x, c)，只要將B[x]加上c，同時C[x]加上c*x即可（根據C[x]和B[x]間的關系可得）；

而ADD(x, c)操作是這樣影響A[1..i]的和的：若x<i，則會將A[1..i]的和加上x*c，否則（x>=i）會將A[1..i]的和加上i*c。也就是，A[1..i]之和 = B[i..N]之和 * i + C[1..i-1]之和。
這樣對于B和C兩個數組而言就變成了“改點求段”（不過B是求后綴和而C是求前綴和）。
另外，該模型中需要特別注意越界問題，即x=0時不能執行SUM_B操作和ADD_C操作！代碼：


操作【1】：
ADD_B(r, c); ADD_C(r, c);
if (l > 1) {ADD_B(l - 1, -c); ADD_C(l - 1, -c);}

操作【2】：SUM(r) - SUM(l - 1)。

代碼1：SAP單路增廣（非遞歸）；

代碼2：SAP多路增廣（遞歸）；

代碼3：Dinic單路增廣（非遞歸）；

代碼4：Dinic多路增廣（遞歸）；

結果：

代碼1：

代碼2：

代碼3：

 代碼4：

結果：
SAP加了多路增廣后，直接秒掉后2個點；
Dinic加了多路增廣后效率差不多，還更低了一點……

（另外發現，SAP的多路增廣不支持當前弧優化……這點和zkw費用流有點像囧……不過效率影響不大……）

總算找到一個相對安靜的地方了……好高欣啊……

希望在這里，本沙茶不要再聽到太多害人的Orz聲（當然，只是別Orz我，神犇們本來就是給人Orz的囧）……

現在沒神馬動力……來這里……就有動力了囧……