fulkerson演算法
❶ 一個非零數乘以一個非零數有哪幾種情況
非零數有正數和負數，相乘有兩種情況，同號相乘結果得正，異號相乘結果得負，希望採納。
❷ 幫我解釋下網路流
必須知識：最短路徑問題
1.Dijkstra
適用於滿足所有權系數大於等於0（lij≥0）的網路最短路問題，能求出起點v1到所有其他點vj的最短距離；
樸素的Dijkstra演算法復雜度為O(N^2)，堆實現的Dijkstra復雜度為O(NlogN).
2.bellman-ford
適用於有負權系數，但無負迴路的有向或無向網路的最短路問題，能求出起點v1到所有其它點 vj的最短距離。bellman-ford演算法復雜度為O(V*E)。
3.Floyed
適用於有負權系數，可以求出圖上任意兩點之間的最短路徑。DP思想的演算法，時間復雜度為O(N^3);
for ( k= 1; k<= n; k++)
for ( i= 1; i<= n; i++)
if (graph[i][k]!=INF)
for ( j= 1; j<= n; j++)
if (graph[k][j]!=INF && graph[i][k]+graph[k][j]< graph[i][j])
graph[i][j]= graph[i][k]+ graph[k][j];
NO.1 s-t最大流
兩大類演算法
1.增廣路演算法
Ford-Fulkerson演算法: 殘留網路中尋找增加路徑
STEP0：置初始可行流。
STEP1：構造原網路的殘量網路，在殘量網路中找s－t有向路。如果沒有，演算法得到最大流結束。否則繼續下一步。
STEP2：依據殘量網路中的s－t有向路寫出對應到原網路中的s－t增廣路。對於增廣路中的前向弧，置s(e)＝u(e)- f(e)。對於反向弧，置s(e)＝f（e） STEP3：計算crement=min{s（e1），s（e2），…，s（ek）}
STEP4：對於增廣路中的前向弧，令f(e)＝f(e)＋crement；對於其中的反向弧，令f(e)＝f(e)-crement，轉STEP1。
關鍵點:尋找可增廣路。決定了演算法復雜度。
實現：Edmonds-Karp 通過採用了廣度優先的搜索策略得以使其復雜度達到O(V*E^2)。
優化—> Dinic演算法(*)
Dinic演算法的思想是為了減少增廣次數，建立一個輔助網路L，L與原網路G具有相同的節點數，但邊上的容量有所不同，在L上進行增廣，將增廣後的流值回寫到原網路上，再建立當前網路的輔助網路，如此反復，達到最大流。分層的目的是降低尋找增廣路的代價。
演算法的時間復雜度為O(V^2*E)。其中m為弧的數目，是多項式演算法。鄰接表表示圖，空間復雜度為O(V+E)。
2.預流推進演算法
一般性的push-relabel演算法: 時間復雜度達到O(V^2*E)。(*)
relabel-to-front演算法->改進
最高標號預流推進:時間復雜度O(V^2*sqrt(E))
NO2. 最小費用最大流
求解最小費用流的步驟和求最大流的步驟幾乎完全一致，只是在步驟1時選一條非飽和路時，應選代價和最小的路，即最短路。
步驟1. 選定一條總的單位費用最小的路，即要給定最小費用的初始可行流，而不是包含邊數最小的路。
步驟2. 不斷重復求最大流的步驟來進行，直到沒有飽和路存在為止。然後計算每個路的總費用。
和Edmonds-Karp標號演算法幾乎一樣，因為這兩種演算法都使用寬度優先搜索來來尋找增廣路徑，所以復雜度也相同，都是O(V*E^2)。
連續最短路演算法 + 線性規劃對偶性優化的原始對偶演算法(*)
傳說中，沒見過，據說復雜度是O(V^3)
NO3. 有上下屆的最大流和最小流（通過添加點來進行轉化）(*)
NO4. 相關圖論演算法
二分圖最大匹配： 加s和t構造最大流
專用演算法：hungary演算法 O(M*N)
二分圖最佳匹配： 加s和t構造最小費用最大流
專用演算法：KM演算法
樸素的實現方法,時間復雜度為O(n^4)
加上鬆弛函數O(n^3)
最小路徑覆蓋：
頂點數－二分圖的最大匹配
s-t最小邊割集：
最大流最小割定理：最小割等於最大流
普通最小邊割集：
Stoer-Wagner Minimum Cut O(n^3)
二分圖的最大獨立集：
N - 二分圖的最大匹配（POJ monthly）girls and boys
反證法證明
普通圖的最大獨立集是np問題。(*)
❸ 高分：網路流問題
一、引言
網路流演算法是一種高效實用的演算法，相對於其它圖論演算法來說，它的模型更加復雜，編程復雜度也更高。但是它綜合了圖論中的其它一些演算法（如最短路徑、寬度搜索演算法），因而適用范圍也更廣，經常能夠很好地解決一些搜索與動態規劃無法解決的非np問題。
網路流在具體問題中的應用，最具挑戰性的部分是模型的構造，它沒用現成的模式可以套用，需要我們對各種網路流的性質了如指掌（比如點有容量、容量有上下限、多重邊等等），根據具體的問題發揮我們的創造性。一道問題經常可以建立多種模型，不同的模型對問題的解決效率的影響也是不同的，本文通過實例探討如何確定適當的模型，提高網路流演算法的效率。
二、網路流演算法時間效率
當我們確定問題可以使用最大流演算法求解後，就根據常用的ford-fulkerson標號法求解；而最小（大）費用最大流問題也可用類似標號法的對偶演算法解題。ford-fulkerson標號法的運行時間為o（ve2），對偶法求最小費用流的運行時間大約為o（v3e2）。
顯然，影響網路流演算法的時間效率的因素主要是網路中頂點的數目與邊的數目。這二個因素之間不是相互獨立的，而是相互聯系，矛盾而統一的。在構造網路模型中，有時，實現了某個因素的優化，另外一個因素也隨之得到了優化；有時，實現某個因素的優化卻要以增大另一因素為代價。因此，我們在具體問題的解決中，要堅持"全局觀"，實現二者的平衡。
三、模型的優化與選擇
(一)減少模型的頂點數與邊數，優化模型
如果能根據問題的一些特殊性質，減少網路模型中的頂點的數目和邊的數目，則可以大大提高演算法的效率。
例1：最少皇後控制
在國際象棋中，皇後能向八個方向攻擊（如圖1(a)所示，圖中黑點格子為皇後的位置，標有k的格子為皇後可攻擊到的格子）。現在給定一個m*n（n、m均不大於於50）的棋盤，棋盤上某些格子有障礙。每個皇後被放置在無障礙的格子中，它就控制了這個格子，除此，它可以從它能攻擊到的最多8個格子中選一個格子來控制，如圖1(b)所示，標號為1的格子被一個皇後所控制。
請你編一程序，計算出至少有多少個皇後才能完全控制整個棋盤。
圖1(a) 圖1(b)
輸入格式：
輸入文件的第一行有兩個整數m和n，表示棋盤的行數與列數。接下來m行n列為一個字元矩陣，用''.''號表示空白的格子，''x''表示有障礙的格子。
輸出格式：
輸出文件的第一行僅有一個數s，表示需要皇後的數目。
sample input
3 4
x...
x.x.
.x..
sample ouput
5
問題分析]
如果本問題用簡單的搜索來做，由於題目給的棋盤很大，搜索演算法很難在短時間內出解。由於一個皇後在棋盤最多隻能控制兩個格子，因此最少需要的皇後數目的下界為[n*m/2]。要使得皇後數目最少，必定是盡量多的皇後控制兩個格子。如果我們在每兩個能相互攻擊到的格子之間加上一條有向弧，則問題很類似於二分圖的最大匹配問題。
[模型一]
1． 將每個非障礙的格子按行優先編號(0~m*n-1)。
2． 將上述的每個格子i折成兩個格子i''和i''''，作為網路模型中的頂點。
3． 若格子i可以攻擊到格子j且i<j，則在模型中頂點i''到j''''之間加上一條有向弧，容量為1。
4． 增加一個源點s，從s點向所有頂點i''添上一條弧；增加一個匯點t，從所有頂點j''''到t添上一條弧，容量均為1。
圖1(b)所示的棋盤，對應的模型為：
圖2
顯然，任一解對應於以上模型的一個最大匹配。且最大匹配中，匹配數必定是偶數。因此至少需要的馬匹數為m＊n－障礙數－最大匹配數/2。
[模型二]
如果我們將棋盤塗成黑白相間的格子，則某皇後控制的兩個格子一定是一個是黑格，另一個是白格（如圖3），不妨設這兩個格子中皇後在白格子上。於是，我們將n*m個格子分成兩部分白格與黑格。因此我們可以將模型一優化為：
圖3
1．將棋盤中的所有格子分成兩個部分，對所有的格子進行編號，每個白格與它能攻擊到的黑格之間（障礙除外）添上一條從白格到黑格的弧，構成一個二分圖。
2．增加一個源點s，從s點向所有非障礙的白格添上一條弧；增加一個匯點t，從所有非障礙的黑格到t添上一條弧。
3．設置所有的弧的流量為1。
圖1(b)所示的棋盤，對應的模型為：
圖4
[兩種模型的比較]
顯然，模型二的頂點數與邊數大致是模型一的一半。下面是在bp環境下兩種模型的時間效率比較(p166/32m)：
模型一 模型二
可擴展性 不易列印出一種解 容易列印出一種解
模型二正是根據問題的特殊性（即馬的走法），將網格中的格點分成白與黑兩類，且規定馬只能從白格跳到黑格，從而避免將每個格點折分成兩個點，減少模型的頂點數，同時也大大減少了邊的數目。達到了很好的優化效果。
(二)綜合各種模型的優點，智能選擇模型
有時，同一問題的各種模型各有特色，各有利弊。這種情況下，我們就要綜合考慮各種模型的優缺點，根據測試數據智能地選擇問題的模型。
例2火星探測器（ioi97）
有一個登陸艙（pod），里邊裝有許多障礙物探測車（mev），將在火星表面著陸。著陸後，探測車離開登陸艙向相距不遠的先期到達的傳送器（transmitter）移動，mev一邊移動，一邊採集岩石（rock）標品，岩石由第一個訪問到它的mev所採集，每塊岩石只能被採集一次。但是這之後，其他mev可以從該處通過。探測車mev不能通過有障礙的地面。
本題限定探測車mev只能沿著格子向南或向東從登陸處向傳送器transmitter移動，允許多個探測車mev在同一時間占據同一位置。
任務：計算出所有探測車的移動途徑，使其送到傳送器的岩石標本的數量最多，且使得所有的探測車都必須到達傳送器。
輸入：
火星表面上的登陸艙pod和傳送器之間的位置用網路p和q表示，登陸艙pod的位置為（1，1）點，傳送器的位置在（p，q）點。
火星上的不同表面用三種不同的數字元號來表示：
0代表平坦無障礙
1代表障礙
2代表石塊。
輸入文件的組成如下：
numberofvehicles
p
q
(x1y1)(x2y1)(x3,y1)…(xp-1y1)(xpy1)
(x1y2)(x2y2)(x3,y2)…(xp-1y1)(xpy2)
(x1y3)(x2y3)(x3,y3)…(xp-1y3)(xpy3)
…
(x1yq-1)(x2yq-1)(x3,yq-1)…(xp-1yq-1)(xpyq-1)
(x1yq)(x2yq)(x3,yq)…(xp-1yq)(xpyq)
p和q是網路的大小；numberofvehicles是小於1000的整數，表示由登陸艙pod所開出的探測車的個數。共有q行數據，每行表示火星表面的一組數據，p和q都不超過128。
[模型一]
很自然我們以登陸艙的位置為源點，傳送器的位置為匯點。同時某塊岩石由第一個訪問到它的mev所採集，每塊岩石只能被採集一次。但是這之後，其他mev可以從該處通過，且允許多個探測車mev在同一時間占據同一位置。因此我們將地圖中的每個點分成兩個點，即（x,y）à(x,y,0)和(x,y,1)。具體的描述一個火星地圖的網路模型構造如下：
1． 將網格中的每個非障礙點分成(x,y)兩個點(x,y,0)和(x,y,1)，其中源點s = v(1, 1, 0),匯點t = v(maxx, maxy, 1)。
2． 在以上頂點中添加以下三種類型的邊e1,e2,e3，相應地容量和費用分別記為c1、c2、c3以及w1、w2、w3:
u e1 = v(x, y, 0) -> v(x, y, 1),c1 = maxint,w1 = 0。
u e2 = v(x, y, 0) -> v(x, y, 1)，c2 = 1，w2 = -1（這里要求(x, y)必須是礦石）
u e3 = v(x, y, 1) -> v(x'', y'', 0)，c3 = maxint,w3 = 0.
其中x''=x+1 y''=y 或x''=x y''=y+1,1 <= x'' <= maxx，1 <= y'' <= maxy，且(x'' y'')非障礙。
從以上模型中可以看出，在構造的過程中，將地圖上的一個點"拆"成了網路的兩個節點。添加e1型邊使得每個點可以被多次訪問，而添加e2型邊使得某點上的礦石對於這個網路，從s到t的一條路徑可以看作是一輛探測車的行動路線。路徑費用就是探測車搜集到的礦石的數目。對於網路g求流量為numberofvehicles的固定最小費用流，可以得到問題的解。
[模型二]
事實上，如果我們只考慮這numberofvehicles輛車中每輛車分別依次裝上哪些礦石。則每輛車經過的礦石就是一條流，因此我們以網格中的礦石為網路的頂點建立以下的網路流模型。
1. 將網格中的每個起點(網格左上角)能到達，且能從它能到達終點(右下角)的礦石 (x,y)點分成左點(x,y,0)和右點(x,y,1)兩個點，並添加源點s和匯點t。
2. 在以上頂點中添加以下五種類型的邊e1,e2,e3，相應地容量和費用分別記為c1、c2、c3以及w1、w2、w3:
u e1 = v(x, y, 0) -> v(x, y, 1),c1 = 1,w1 = -1。
u e2 = v(x, y, 1) -> v(x'', y'', 0)，c2 = 1，w2 = 0（礦石點(x, y)可到達礦石點(x'',y'')）。
u e3 = s -> v(x, y, 0)，c3 = 1,w3 = 0。
u e4 = v(x, y, 1)->t，c4 = 1,w4 = 0。
u e5=s->t,c5=maxint,w5=0。
由於每個石塊被折成兩個點，且容量為1，就保證了每個石塊只被取走一次，同時取走一塊石塊就得到-1的費用。因此對以上模型，我們求流量為numberofvehicles的最小費用流，就可得到解。
[兩種模型的比較]
1.模型一以網格為頂點，模型二以礦石為頂點，因此在頂點個數上模型二明顯優於模型一，對於一些礦石比較稀疏，而網格又比較大的數據，模型二的效率要比模型一來得高。且只要礦石的個數不超過一定數目，模型二可以處理p，q很大的數據，而模型一卻不行。
2．模型一中邊的數目最多為3*p*q，而模型二中邊的數目最壞情況下大約為p*q*(p+1)*(q+1)/4-p*q。因此在這個問題中，若對於一些礦石比較密集且網格又比較大的數據，模型二的邊數將大大超過模型一，從而使得時間效率大大低於模型一。
下面是網格中都是礦石的情況比較（piii700/128m ，bp7.0保護模式）：
numberofvehicles＝10 模型一 模型二
通過以上數據，可知對於p，q不超過60的情況，模型一都能在10秒內出解。而模型二則對於p、q＝30的最壞情況下速度就很慢了，且p、q超過30後就出現內存溢出情況，而無法解決。
因此，對於本題，以上兩種模型各有利弊，我們可根據測試數據中礦石稀疏程度來決定建立什麼樣的模型。若礦石比較稀疏，則可以考慮用建立如模型二的網路模型；若礦石比較密集則建立模型一所示網路模型。然後，再應用求最小費用最大流演算法求解。對於p，q＞60，且礦石比較多情況下，兩種模型的網路流演算法都無法求解。在實際的應用中問題經常都只要求近似解，此時還可用綜合一些其它演算法來求解。
四、結束語
綜上所述，網路流演算法中模型的優化是網路流演算法提高效率的根本。我們要根據實際問題，從減少頂點及邊的角度綜合考慮如何對模型進行優化，選擇適當的模型，以提高演算法的效率。對於有些題目，解題的各種模型各有優劣時，還可通過程序自動分析測試數據，以決定何種情況下採用何種模型，充分發揮各種模型的優點，以達到優化程序效率的目的。
❹ 最大流問題與演算法ford-fulkerson
最重要的就是殘余網路
所謂的殘余網路就是說在原圖的基礎上，每條邊流量減去已經擴充過的流量值。
然後在這個圖中任意找一條路徑，然後一直將其流量擴充到總流量中，至到找不到這樣的路徑(從原點到匯點的正流量路徑)，演算法結束。
重點在於殘余網路的數據結構表示以及其維護方法，路徑搜索的方法則可以隨便發揮。。
❺ c/c++ 最大流演算法ford-fulkerson
你的問題是用C/C++寫最大流演算法ford-fulkerson演算法。頂點就是節點。
void maximum_flow(int n, int s, int t, int *capacity, int *flow)
可以參考：演算法模板-最大流（Ford-fulkerson演算法）
❻ 什麼是距離矢量協議
距離矢量路由協議 路由以矢量（距離、方向）的方式被通告出去的，其中距離是根據度量來定義的，方向是根據下一跳路由器定義的。被認為是「依照傳聞進行路由選擇」。 以下都屬於距離矢量協議： 1、 RIP 2、 Xerox網路系統的XNS RIP 3、 NOVELL的IPX RIP 4、 IGRP 5、 DNA4 6、 APPLE TALK的路由表維護協議RTMP
❼ 如何證明Ford-Fulkerson網路流演算法的正確性
最大流理論是由福特和富爾克森於 1956 年創立的 ，他們指出最大流的流值等於最小割(截集)的容量這個重要的事實，並根據這一原理設計了用標號法求最大流的方法，後來又有人加以改進，使得求解最大流的方法更加豐富和完善 。最大流問題的研究密切了圖論和運籌學，特別是與線性規劃的聯系，開辟了圖論應用的新途徑。
❽ 距離矢量協議的路由演算法
距離矢量路由演算法是動態路由演算法。它是這樣工作的：每個路由器維護一張矢量表，表中列出了當前已知的到 每個目標的最佳距離，以及所使用的線路。通過在鄰居之間相互交換信息，路由器不斷地更新它們內部的表。
距離矢量路由演算法最常見的是Ford－Fulkerson演算法。該演算法的核心思想是使用標號的方法不斷尋找一個圖上的 可增廣路徑並且進行調整，直到找不到可增廣路徑為止。距離矢量路由演算法號召每個路由器在每次更新時發送它 的整個路由表，但僅僅給它的鄰居。距離矢量路由演算法傾向於路由循環，但比鏈路狀態路由演算法計算更簡單。
演算法描述如下：
給定帶杈有向圖G和源點s，求從s到G中任意頂點v的最短路徑，該演算法通過在一個路由中重申跳數的個數九來尋 找一個最短路徑生成樹。
在距離矢量路由選擇演算法中，每個路由器維持有一張子網中每一個以其他路由器為索引的路由選擇表，表中的 每一個項目都對應於子網中的每個路由器。此表項包括兩個部分，即希望使用的到目的地的輸出線路和估計到達 目的地所需時間或距離。用度量標准可為站點，估計的時間延遲（ms），該路出排隊的分組估計總數或類似的值。
假定路由器知道它到每個相鄰路由器的「距離」。如果度量標准為站點，其距離就為一個站點；如果度量標準是隊列長度，則路由器會簡單地檢查每個隊列；如果度量標準是延遲，路由器可以直接發送一個特別「響應」（ECHO）分組來測出延遲，接收者只對它加上時間標記後就盡快送回。
