福州一中肖漢駿
「許多問題可以先轉化為網路流問題，再運用最大流演算法加以解決。而發現問題本質，根據最大流演算法的特點，設計與之相配的數學模型是運用最大流演算法解決問題的重要步驟。」
「網路流在具體問題中的應用，最具挑戰性的部分是模型的構造。這沒用現成的模式可以套用，需要對各種網路流的性質瞭如指掌（比如點有容量、容量有上下限、多重邊等等），並且歸納總結一些經驗，發揮我們的創造性。」
注：本文大部分出自江濤老師講稿及網路資料
如同我們可以把乙個實際的道路地圖抽象成乙個有向圖來計算兩點之間的最短路徑，我們也可以將乙個有向圖看作乙個流網路來解決另一型別的問題。流網路比較適合用來模擬液體流經管道、電流在電路網路中的運動、資訊網路中資訊的傳遞等等類似的過程。
乙個例項：運輸網路
參看下圖，給定乙個有向圖g=(v,e)，把圖中的邊看作管道，每條邊上有乙個權值，表示該管道的流量上限。給定源點s和匯點t，現在假設在s處有乙個水源，t處有乙個蓄水池，問從s到t的最大水流量是多少，類似於這類的問題都可歸結為網路流問題。
在流網路中，每條有向邊可以被看導管。每根導管有乙個固定的容量，代表物質流經這個導管的最大速率，例如乙個管道每小時最多能流過200加侖液體或者一根電線最多能承載20安培的電流。流網路中的頂點可以看作是導管的連線處。
除了源點和匯點之外，物質流進每個點的速率必須等於流出這個點的速率。如果我們把研究的物質特化為電流，這種「流的保持」屬性就好像電路中的基爾霍夫電流定律一樣。
乙個有向圖 g=(v，e)；
有兩個特別的點：源點s、匯點t；
圖中每條邊(u,v)∈e，有乙個非負值的容量c(u,v)
記為 g=(v，e，c)，網路三要素：點、邊、容量
是網路g上的乙個「流」，即每條邊上有個「流量」p(u,v)，要滿足下面兩個條件：
對任意弧(u,v)---有向邊
除源點和匯點，對任意中間點有：流入u的「流量」與流出u的「流量」相等。即：
乙個s-t割是這樣乙個邊的集合，把這些邊從網路中刪除之後，s到t就不可達了。或者，正式的說，乙個割把頂點集合分成a,b兩個集合，其中s在a中,t在b中，而割中的邊就是所有從a出發，到達b的所有邊。
割的容量就是割中所有邊的容量的和。正式的說，就是所有從a到b的邊的容量的和。
源點的淨流出「流量」 或匯點的淨流入「流量」。即：
注意，我們這裡說的流量是一種速率，而不是指總量。聯絡上面所說的例項，下面是乙個流量為1的可行流：
下面我們用數學語言來進行相關概念的定義：
設g=(v,e)是乙個流網路，設c(u,v)>＝0表示從u到v的管道的流量上限。設s為源，t為匯。g的流是乙個函式f:v×v→r，且滿足下面三個特徵：
由於引入了斜對稱性，我們可以通過指定反向邊的容量為0，統一地處理退流情況。若處理最小費用最大流，則反向邊的費用為正向邊的費用的相反數。
尋找網路g上可能的最大流量(和乙個有最大流量的可行流方案)，即為網路g上的最大流問題。它是網路流問題中最基本的問題，而網路流問題又可以歸結為一類特殊的線性規劃問題。
解決最大流問題的常用到ford-fulkerson方法，之所以稱其方法而不是演算法，是因為在這種思想下包含著若干種時間複雜度不同的實現，其中較多地是使用edmonds-karp演算法。
與此相對，push-relabel演算法採用了與ford-fulkerson方法完全不同的思考角度，降低了漸進意義下的時間複雜度。而relabel-to-front演算法則是對push-relabel演算法的改良和精煉，效率更佳。
關於這三種常用演算法的時間複雜度可見下表：（其中v表示圖的頂點數，e表示邊數）
可以看出，當給定的有向圖比較稀疏時，三種演算法的效率不會相差太多，但當網路稠密時，relabel-to-front演算法在效率上有著明顯的優勢。
求解過程中的困惑：
[問題1]流量還可能增加嗎？
[問題2]如果能增加，怎樣改進？
退流的概念——後向弧
仔細分析圖4.1，我們發現，流量是可以增加的：
把乙個流量弧(b,c)和(c,t)上的流退回到b點，改道從b-d-e-t走，就可以增加流量了，如下圖：
圖4.1不能「直接尋找增大流的路徑」，是因為當初有些弧上的流選擇不「恰當」，要「退流」。
一種直觀的想法就是：調整或重新搜尋「當初的選擇」——難！
能不能保留以前的工作，而在這之上改進呢？經過專家們研究發現，加入退流思想——後向弧，就能再次「直接尋找增大流的路徑」。
若p是網路中鏈結源點s和匯點t的一條路，我們定義路的方向是從s到t，則路上的弧有兩種：
前向弧——弧的方向與路的方向一致。前向弧的全體記為p+；
後向弧——弧的方向與路的方向相反。後向弧的全體記為p-；
設f是乙個可行流，p是從s到t的一條路，若p滿足下列條件：
在p+的所有前向弧(u,v)上，0<=f(u,v)在p-的所有後向弧(u,v)上，0則稱p是關於可行流f的一條可增廣路徑。
本圖中：s-a-c-b-d-e-t為一增廣路徑。其中(c,b)為後向弧，其它為前向弧。
求路徑可改進量；
修改增廣路徑上的流量；
由於要考慮前向、後向弧，分析、描述時不簡潔，直接在圖上看也不容易看出增廣路徑。
因此我們把已經有的流量從容量中分離出來表示，引入乙個與原問題等價的殘留網路。
其中，前向弧(黑色)上的容量為「剩餘容量」=c(u,v)-f(u,v)；後向弧(紅色)上的容量為「可退流量」=f(v，u)。
改造後的網如下：
在這張圖上，我們找增廣路徑顯的非常直觀了!
結合增廣路徑，我們有如下定理：
最大流-最小割定理：如果殘留網路上找不到增廣路徑，則當前流為最大流；反之，如果當前流不為最大流，則一定有增廣路徑。最大流值對應最小割。
任何圖中，從s到t的最大流等於所有(s,t)割的容量的最小值。
一般的ford-fulkerson方法具有迭代性質，我們把頂點u和v之間的流記作f(u,v)。那麼在最開始，我們對所有的u,v∈v置f(u,v)=0。在每次的迭代過程中，通過找到一條增廣路徑來使|f|增加。
在這裡，我們可以簡單地認為所謂的「增廣路徑」就是一條可以傳送比當前更多流的從源點s到匯點t的路徑，一旦找到了這樣的路徑，我們就可以得到乙個比原流流量更大的新流。重複這個過程，直到不存在增廣路徑為止，這就是ford-fulkerson方法的主要過程，可以用偽碼表示如下：
實現ford-fulkerson的時間複雜度主要取決於如何尋找增廣路徑p。常見的有深度搜尋dfs、寬度搜尋bfs以及優先搜尋pfs——即類似dijkstra演算法的標號法。edmonds-karp實現正是通過採用了bfs的搜尋策略得以使其複雜度達到o(v*e2)。
很多漸進意義下最優的演算法都是採用了push-relabel演算法的思想，而且很多其他的相關問題，比如最小費用流問題，也可以用這種方法很好的解決。首先介紹的是一般性的push-relabel演算法。
不同於ford-fulkerson方法在殘留網路中尋找增廣路徑的方式，push-relabel演算法在執行的過程中只關注某乙個頂點以及它的相鄰頂點，在這個過程中，它並不像ford-fulkerson方法保持著「流的保持」性質，而是以乙個「先流」進行運作。這個先流同樣是乙個v×v→r的函式，滿足容量限制和斜對稱性，同時，它對所有的u∈v-滿足f(v,u)>=0。我們記e(u)=f(v,u)。
如果e(u)>0我們就說頂點u溢位。
為了步入正題，我們還需要介紹push-relabel演算法引入的乙個額外的高度函式。設g=(v,e)是乙個流網路，源點是s，匯點是t，f是g中的乙個先流。如果函式h:
v→n滿足h(s)=|v|，h(t)=0，而且對殘留網路中所有的邊(u,v)有h(u)<=h(v)+1，那麼稱h是乙個高度函式。
正如其名稱一樣，push-relabel演算法有兩個基本操作:push和relabel。一般性的push-relabel演算法就是通過往復執行這兩種操作完成的：
下面具體介紹一下這兩個基本操作。
2019防流 控流總結
2009 2010學年度 普及九年義務教育 防流 控流 總結 為了進一步推進素質教育的健康發展，確保適齡兒童完成九年義務教育，我校高度重視防流控流工作，認真執行上級有關檔案精神，並做了大量工作，現將我校 防流控流 工作情況總結如下 一 強化措施，落實責任，增強了全體教師的責任感和使命感。校長與班主任...
製作模型總結
展示模型製作實踐 報告班級 建築0902 姓名 黃爽 學號 20094437 指導老師 梁茵 日期 2010.1.11.一 實踐目的 本次實踐是建築學專業的綜合性實踐教學環節，旨在培養學生的實際動手能力。其主要任務是使學生理解模型製作在作品設計中的重要性，掌握模型製作的基本工具 方法和過程，鍛鍊學生...
控流情況總結
通過學期末的工作檢查，我鎮小學的控流工作，在全鎮教職工的共同努力下，取得了較好的成績，其表現為 措施到位，包保責任制健全，全鎮小學生無流失，班級控流袋三單健全 清楚，數學準確 相符，控流工作管理走上了正規，希望在今後的工作中，保持下去，繼續做好此項工作。從檢查上看，控流工作個別老師還存在著一定的問題...