【正文】 .。算法思想：隨便構(gòu)造一個可行頂標(biāo)（例如Y結(jié)點頂標(biāo)為0，X結(jié)點的頂標(biāo)為它出發(fā)所有弧的最大權(quán)值，然后求相等子圖的最大匹配）若存在完美匹配，算法終止否則修改頂標(biāo)使得相等子圖的邊變多，有更大機會存在完美匹配Kuhn和Munkras . 一般圖General Graph. 無權(quán)圖帶花樹算法 Unweighted Blossom (Edmonds)朱(永津)劉(振宏)算法（1965）Edmons算法（1968）Dictionary of Algorithms and Data Structures NISTWikipediaIntroduction to Algorithm單純的課本內(nèi)容，并不能滿足學(xué)生的需要，通過補充，達到內(nèi)容的完善 教育之通病是教用腦的人不用手，不教用手的人用腦，所以一無所能。(2)是根據(jù)可行頂標(biāo)定義。證明：設(shè)M*是相等子圖的完美匹配，M是原圖的任意完美匹配。引入相等子圖：G的生成子圖，包含所有點，但只包含滿足的所有弧。習(xí)題：Ural 1203 Conference (最小點覆蓋). 無權(quán)圖匈牙利算法 Unweighted Hopcroft and Karp algorithm匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出。這個定理適用于任意圖。所以最小費用流問題是P類的。但實際上，會比這個快多了。設(shè)c為容量最大值，w為費用最大值。3. 沿著找到的負(fù)費用圈改進殘量網(wǎng)絡(luò)。算法：1. 用最大流算法求出網(wǎng)絡(luò)的任一個最大流的殘量網(wǎng)絡(luò)。習(xí)題：FJOI 2002 蚯蚓問題. 找負(fù)權(quán)圈 Finding negative circle在最大流的殘量網(wǎng)絡(luò)中不斷的找負(fù)費用圈并沿著它增廣，直到不存這樣的負(fù)圈。轉(zhuǎn)2。算法：1. 用BellmanFord在殘量網(wǎng)絡(luò)中求st的最小費用路，若不存在，結(jié)束；否則轉(zhuǎn)2。下面是最小費用流問題的數(shù)學(xué)模型的表述： 最小費用最大流問題：總流量d為網(wǎng)絡(luò)的最大流的最小費用流問題。 因為樸素的預(yù)流推進算法O(N3)，總復(fù)雜度為O(N3 log2流量) 。這樣就可以求出最大流。證明：如果從s到t的最大流量為amax，那么從t到s連一條下界b(t, s) = a’ amax的弧(t, s)，則從在這個改造后的圖中一定沒有無源匯的可行流：否則將這個可行流中的弧(t, s)除去，就得到了原圖中s到t的流量為a’的流，大于最大流量amax，產(chǎn)生矛盾。問題[3]與問題[4]的另一種簡易求法：注意問題[2]中，構(gòu)造出的(t, s)，上下界幾乎沒什么限制。2. 從T到S找增廣軌，不斷反著改進。這樣既不破壞下界(分離出來)也不超出上界(第2步滿足容量限制)，問題解決。3. 最后將暫時刪去的下界信息恢復(fù)，合并到當(dāng)前圖中。再將(T,S)刪去，恢復(fù)源匯。若可行無解，則退出。問題[2] 求有源匯的網(wǎng)絡(luò)有上下界的可行流12st2,63,73,4加入邊(t, s)，下界為0(保證不會連上附加源匯x, y)，不限上界，將問題[2]轉(zhuǎn)化為問題[1]來求解。若去掉(y, x)后，附加源x到附加匯y的最大流，能使得x的出弧或者y的入弧都滿，充要于原圖有可行流。這樣就建立了一個等價的網(wǎng)絡(luò)。+∞12st441233 由于必要弧的有一定要滿的限制，將必要弧“拉”出來集中考慮：+∞12st441233 添加附加源x, 附加匯y。必要弧的構(gòu)造，將容量下界的限制分離開了，從而構(gòu)造了一個沒有下界的網(wǎng)絡(luò)G’：1． 將原弧(u,v)分離出一條必要?。?。將這類問題由易到難一一解決：問題[1] 求無源匯的網(wǎng)絡(luò)有上下界的可行流12st2,63,73,4+∞由于下界是一條弧上的流必需要滿足的確定值。而我們可以在O(m)的時間內(nèi)重新計算新的層次圖，所以我們就可以在O(n m + n n^2)時間完成整個算法，也就是O(n^3)。對于a），因為我們每次充滿一條邊就會把它從圖中刪除，所以a）的總時間是O(m)。為了得到我們需要的界，我們需要這樣一個性質(zhì)：當(dāng)我們在上面的對每個新的頂點v執(zhí)行算法的步驟中，保證對每條邊我們只檢查一次，對其做完所有需要的操作之后才會去做下一條邊。這樣，我們剛才處理的過程就容易得到下面的下面所謂的性質(zhì)了。（* daizinnd，想了好久才明白具體怎么做的首先，為了從s運送c到v，我們從v開始向上考慮，把任意一條從v向上的邊給充滿，如果不能夠充滿，說明還沒有安置的流量就這些了，全部扔在這條邊上就是了，為什么一定能夠找到這樣一條邊呢，：）然后假設(shè)我們剛才填充的這條邊是uv，那么我們就有一些流量需要在u繼續(xù)往上進行處理，使用剛才在v點同樣的辦法，直到一直處理到了s，一路上肯定是不會出現(xiàn)什么障礙的。你可能覺得這不又回到原來的問題了么？但是，這里有點值得注意：因為v具有最小的容量，我們可以使用任何的貪心策略來從其他頂點流入流出c的流量而不會被堵住。如果他的容量是0，oh yeah我們就可以把他和與他相關(guān)聯(lián)的邊都刪除掉，并且更新他的鄰居的容量值。我們定義c(v)=頂點v的容量：也就c_in[v],c_out[v]的最小值，這里c_in[v]是所有v的入邊的容量的和，而c_out[v]類似。術(shù)語：一個充滿了這個剩余圖的流稱之為塊流。為了做到這個，我們看前面得到的層次圖（我們不考慮所有的后向邊以及兩個端點在同一層的邊）。下面我們試著降到O(n^3)。習(xí)題：Ural 1277 Cops and Thieves (最小切割最大流). 基本算法 Basic algorithms. FordFulkerson method增廣軌定理：. EdmondsKarp algorithm. Minimum length path. Maximum capability path. 預(yù)流推進算法 Preflow push method. Pushrelabel. Relabeltofront. Dinic methodDINIC amp。 其中(1)表示要求從源流出的流量要最大。其中(4)可以改寫成：稱為流量平衡條件。最大流問題的數(shù)學(xué)模型描述如下：其中(2)，為容量限制條件：邊的流量不超過邊上的容量。參考文獻：[1] Johnson39。(2)令路徑，則只與以及首尾的標(biāo)號h有關(guān)，不影響的決策。權(quán)值改造滿足兩個原則：(1)W’ 非負(fù)；(2)對于任意頂點u, v，p是在W上的u到v的最短路當(dāng)且僅當(dāng)p是在W’上的u到v的最短路。O(m)3. 對于每個結(jié)點，用一次以Fibonacci Heap為優(yōu)先隊列的Dijkstra算法，可求出與其他頂點的最短路。對用BellmanFord，若有負(fù)圈，則結(jié)束；否則可以得到，即到的最短路長。若圖中有負(fù)權(quán)，但沒有負(fù)圈，則可以把權(quán)值W改造成W’，W’非負(fù)，使得能夠使用Dijkstra算法。本算法用了權(quán)值改造(reweighting)技術(shù)。算法復(fù)雜度：. Johnson本算法適用于稀疏圖。若發(fā)現(xiàn)某個節(jié)點u使得, 則說明網(wǎng)絡(luò)本來就含有負(fù)有向圈，結(jié)束。二維數(shù)組，記錄u到v，最后經(jīng)過哪個k的迭代。假設(shè)對k成立,下面考慮k+1的情況；從u到v 且不通過k+1,…, n 節(jié)點的最短路有兩種可能：(1)不經(jīng)過k節(jié)點，即為；(2)經(jīng)過k節(jié)點，即為。復(fù)雜度：. 所有頂點對間最短路 Allpairs shortest paths. 基本算法 Basic algorithms. FloydWarshall本質(zhì)就是用迭代法（動態(tài)規(guī)劃）：表示u到v的不經(jīng)過k,k+1,…,n結(jié)點(除u,v外)時，從u,v的最短路長。(u,v)，對(u,v)進行松弛操作，即若，則改進，pred(v)=u。習(xí)題：NOI 1999 01串. 有向無環(huán)圖上的最短路 Shortest paths in DAG算法：1. 。W：， 對進行BellmanFord算法，可以得到，令，即為所求，其中C是任意一個常數(shù)，均滿足原不等式組。于是可以構(gòu)造一個有向網(wǎng)絡(luò)G=(V,E,W)，稱為約束圖(constraints graph)。即。矩陣A每行含一個1一個1，其他都是0。習(xí)題：Ural 1254 Die Hard （可斜走的網(wǎng)格最短路）。算法復(fù)雜度理論上同BellmanFord，O(nm)，但實際上卻是O(km)。SPFA在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之后再次被放入隊列，也就是一個點改進過其它的點之后，過了一段時間可能本身被改進，于是再次用來改進其它的點，這樣反復(fù)迭代下去。由于點可能多次入隊，但隊列中同時不會超過n個點。若，則改進，pred(v)=u，由于減少了，v可能在以后改進其他的點，所以若v不在Q中，則將v入隊。algorithm(SPFA)SPFA 其實就是BellmanFord的一種隊列實現(xiàn)，減少了冗余，即松馳的邊至少不會以一個d為∞的點為起點。path適用范圍：一般圖?？梢宰C明算法一定在n1步迭代后收斂；否則一定有負(fù)權(quán)圈。若沒有邊被松弛，則算法結(jié)束。由于第k+1次迭代過程中，不會影響k次的迭代結(jié)果，d用O(n)的空間即可。下面用歸納法證明：k=1顯然成立。. BellmanFord采用了標(biāo)號修正算法(LabelCorrecting)。若用Binary Heap則。這里的d可以用優(yōu)先隊列實現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。松弛，即若，則改進，pred(v)=u。若u取不到，即d(u)=∞則結(jié)束；否則標(biāo)記為已檢查，即。下文稱永久標(biāo)號為已檢查。. 基本算法 Basic algorithms. Dijkstra采用了標(biāo)號設(shè)定算法(LabelSetting)。標(biāo)號修正算法(LabelCorrecting)：每次迭代時并不一定將任何頂點標(biāo)號從臨時標(biāo)號轉(zhuǎn)變?yōu)橛谰脴?biāo)號，只是對臨時標(biāo)號進行一次修正，所有頂點標(biāo)號仍然都是臨時標(biāo)號；只有在所有迭代終止時，所有頂點標(biāo)號同時轉(zhuǎn)變?yōu)橛谰脴?biāo)號。當(dāng)算法結(jié)束時，距離標(biāo)號表示的是從起點到該頂點的最短路長度。最短路算法求解過程中的標(biāo)號規(guī)定：對于V 中每一個頂點v，設(shè)置一個標(biāo)號：距離標(biāo)號d(v) ，記錄的是從起點到該頂點的最短路長度的上界；再設(shè)置一個是前趨pred(v)，記錄的是當(dāng)起點s到該頂點v的一條路長取到該上界時，該條路中頂點v 前面的那個直接前趨。直觀的講，就是路徑最后通過(u,v)，使得s到v的距離比原來s到v的方案的距離短。當(dāng)某弧(u,v)位于最短路上時，一定有。令d(v)為s到v的最短路長度上界。習(xí)題：Ural 1