摘要： POJ 1459http://poj.org/problem?id=1459題意：給幾個發電站，給幾個消耗站，再給幾個轉發點。發電站只發電，消耗站只消耗電，轉發點只是轉發電，再給各個傳送線的傳電能力。問你消耗站能獲得的最多電是多少。//方法如下： //虛擬出源點0和匯點n+1; 將所有的源點與0相連，將所有的匯點和n+1相連 #include <iostream>#include <cstring>using namespace std;const int inf = 100000000;const int maxN = 105;int n, np, nc, m, l[ 閱讀全文

摘要： 最大流的算法——Edmonds-Karp算法(最短路徑增廣算法)這里介紹一個最簡單的算法:Edmonds-Karp算法即最短路徑增廣算法簡稱EK算法EK算法基于一個基本的方法:Ford-Fulkerson方法即增廣路方法簡稱FF方法增廣路方法是很多網絡流算法的基礎 一般都在殘留網絡中實現其思路是每次找出一條從源到匯的能夠增加流的路徑調整流值和殘留網絡 不斷調整直到沒有增廣路為止FF方法的基礎是增廣路定理(Augmenting Path Theorem):網絡達到最大流當且僅當殘留網絡中沒有增廣路要實現這個算法，就遇到了三個問題：(1)最多要增廣多少次?可以證明 最多O(VE)次增廣 可以達到最 閱讀全文

摘要： 一、網絡流的三個基本性質：1.容量限制如果C代表每條邊的容量 F代表每條邊的流量一個顯然的實事是F小于等于C 不然水管子就爆了這就是網絡流的第一條性質容量限制:F<x,y> ≤ C<x,y>2.流量守恒再考慮節點任意一個節點 流入量總是等于流出的量 否則就會蓄水(爆炸危險...)或者平白無故多出水(有地下水涌出?)這是第二條性質流量守恒:Σ F<v,x> = Σ F<x,u>3.斜對稱性最后一個不是很顯然的性質 是斜對稱性: F<x,y> = - F<y,x>這其實是完善的網絡流理論不可缺少的 就好比中學物理里用正負數來定 閱讀全文