引入： 圖論中的一種理論與方法，研究網絡上的一類最優化問題 。 很多系統中涉及流量問題，例如公路系統中車流量，網絡中的數據信息流，供油管道的油流量等。我們可以將有向圖進一步理解為“流網絡”(flow network)，并利用這樣的抽象模型求解有關流量的問題。 一：最大流 1.簡介 求解網絡流的基本思想就是每次尋找增廣路(就是源點到匯點的一條可行路)然后ans+=增廣路能流過的流量，更新剩余網絡，然后再做增廣路，直到做不出增廣路。關于網絡流入門最難理解的地方就是剩余網絡了….為什么在找到一條增廣路后…不僅要將每條邊的可行流量減去增廣路能流過的流量…還要將每條邊的反向弧加上增廣路能流過的流量.?..原因是在做增廣路時可能會阻塞后面的增廣路…或者說做增廣路本來是有個順序才能找完最大流的…..但我們是任意找的…為了修正…就每次將流量加在了反向弧上…讓后面的流能夠進行自我調整…剩余網絡的更新(就在原圖上更新就可以了) 最大流算法： 首先來看若干個概念 （1）流網絡G=(V,E)是一個有向圖，其中每條邊(u,v)∈E均有一個非負容量c(u,v)>=0。如果(u,v)不屬于E，則假定c(u,v)=0。流網絡中有兩個特別的頂點：源點s和匯點t。 （2） 對一個流網絡G=(V,E)，其容量函數為c，源點和匯點分別為s和t。G的流f滿足下列三個性質： 容量限制：對所有的u，v∈V，要求f(u,v)<=c(u,v)。 反對稱性：對所有的u，v∈V，要求f(u,v)=-f(v,u)。 流守恒性：對所有u∈V-{s,t}，要求∑f(u,v)=0 (v∈V)。 容量限制說明了從一個頂點到另一個頂點的網絡流不能超過設定的容量，就好像是一個管道只能傳輸一定容量的水，而不可能超過管道體積的限制；反對稱性說明了從頂點u到頂點v的流是其反向流求負所得，就好像是當參考方向固定后，站在不同的方向看，速度一正一負；而流守恒性說明了從非源點或非匯點的頂點出發的點網絡流之和為0。一般的最大流問題就是在不違背上述原則的基礎上求出從源點s到匯點t的最大的流量值，顯然這個流量值應該定義為從源點出發的總流量或是最后聚集到t的總流量，即流f的值定義為|f|=∑f(s,v) (v∈V)。 （3）殘留網絡 在給定的流網絡G=(V,E)中，設f為G中的一個流，并考察一對頂點u，v∈V，在不超過容量c(u,v)的條件下，從u到v之間可以壓入的額外網絡流量，就是(u,v)的殘留容量，就好像某一個管道的水還沒有超過管道的上限，那么就這條管道而言，就一定還可以注入更多的水。殘留容量的定義為：cf(u,v)=c(u,v)-f(u,v)。而由所有屬于G的邊的殘留容量所構成的帶權有向圖就是G的殘留網絡 （4）增廣路徑 增廣路徑p為殘留網絡Gf中從s到t的一條簡單路徑。根據殘留網絡的定義，在不違反容量限制的條件下，G中所對應的增廣路徑上的每條邊(u,v)可以容納從u到v的某額外正網絡流。而能夠在這條路徑上的網絡流的最大值一定是p中邊的殘留容量的最小值。 1：EK算法 EK算法基于一個基本的方法:Ford-Fulkerson方法 即增廣路方法 簡稱FF方法 增廣路方法是很多網絡流算法的基礎 一般都在殘留網絡中實現 其思路是每次找出一條從源到匯的能夠增加流的路徑 調整流值和殘留網絡 不斷調整直到沒有增廣路為止 FF方法的基礎是增廣路定理(Augmenting Path Theorem):網絡達到最大流當且僅當殘留網絡中沒有增廣路 EK算法的思路非常的簡單，就是一直找增廣路徑（BFS），假如有，記錄增廣路的最小值k，ans+=k ，并更新殘量網絡（要加反向弧） EK算法的時間復雜度是O(m^2n) 最多增廣mn次,bfs復雜度O(m) 下面來段代碼模板：
#include <iostream> #include <queue> #include <cstring> using namespace std; #define arraysize 201 int maxData = 0x7fffffff; int capacity[arraysize][arraysize]; //記錄殘留網絡的容量 int flow[arraysize]; //標記從源點到當前節點實際還剩多少流量可用 int PRe[arraysize]; //標記在這條路徑上當前節點的前驅,同時標記該節點是否在隊列中 int n,m; queue<int> myqueue; int BFS(int src,int des) { int i,j; while(!myqueue.empty()) myqueue.pop(); //隊列清空 for(i=1;i<m+1;++i) pre[i]=-1; //初始化前驅 pre[src]=0; //源點的前驅是0 flow[src]= maxData; //源點具有無限大的流量 myqueue.push(src); //進隊 while(!myqueue.empty()) //隊列不為空 { int index=myqueue.front(); //獲取隊首 myqueue.pop(); if(index == des) break; //找到了增廣路徑 [終點] for(i=1;i<=m;++i) { if(i!=src && capacity[index][i]>0 && pre[i]==-1) { //不是源點 有容量 不在隊列 pre[i] = index; //記錄前驅 flow[i] = min(capacity[index][i],flow[index]); //關鍵：迭代的找到增量 //printf("ind:%d i:%d flowi:%d cap:%d flowind:%d/n",index,i,flow[i],capacity[index][i],flow[index]); myqueue.push(i); } } } if(pre[des]==-1) return -1; //殘留圖中不再存在增廣路徑 else return flow[des]; //返回這條路的流量 } int maxFlow(int src,int des) { int increasement= 0; int sumflow = 0; while((increasement=BFS(src,des))!=-1) { int k = des; //利用前驅尋找路徑 while(k!=src) { int last = pre[k]; capacity[last][k] -= increasement; //改變正向邊的容量 capacity[k][last] += increasement; //改變反向邊的容量[關鍵] k = last; } sumflow += increasement; } return sumflow; } int main() { int i,j; int start,end,ci; while(scanf("%d%d",&n,&m)!=EOF) { memset(capacity,0,sizeof(capacity)); memset(flow,0,sizeof(flow)); for(i=0;i<n;++i) { scanf("%d%d%d",&start,&end,&ci); if(start==end) //考慮起點終點相同的情況 continue; capacity[start][end] +=ci; //此處注意可能出現多條同一起點終點的情況 } cout<<maxFlow(1,m)<<endl; } return 0; }2：Dinic算法
1、初始化流量，計算出剩余圖 2、一次bfs對頂點標號，計算出層次圖，如果匯點不在層次圖內，那么算法結束 3、一次dfs過程找增廣 4、轉步驟 2 頂點u的層次：level(u)=在剩余圖中從源點到u所經過的最少邊數 層次圖：對于剩余圖中的任意一條邊(a,b), 當且僅當level(a)+1=level(b)時,(a,b)是層次圖中的邊 
復雜度O(n2*m) 程序簡短 對于較大規模的數據實際速度很快 代碼：
3：ISAP 之前的兩種算法是SAP算法，這里介紹一下ISAP算法 算法基于這樣的一個事實：每次增廣之后，任意結點到匯點（在殘余網絡中）的最短距離都不會減小。這樣，我們可以利用d[i[表示結點i到匯點的距離的下界。然后再增廣過程當中不斷地修改這個下界。增廣的時候和Dinic算法類似，只允許沿著d[i]==d[j]+1的弧(i,j)走。 不難證明，d[i]滿足兩個條件：(1)d[t]=0;(2)對任意的弧(i,j) d[i]≤d[j]+1。因為最壞的情況就是s到t是一條鏈，此時等號成立。因此，當d[s]≥n時，殘余網絡中不存在s-t路。 那么與Dinic算法類似，事先逆向bfs，找增廣的過程就是沿著“允許弧”（即滿足f< c且d[i]==d[j]+1的弧）往前走。（稱為“前進”）。如果向前走不動了，那么就要考慮原路返回（稱為“撤退”）。此時把d[i]修改為min{d[j]}+1即可。因為要滿足d函數的條件(2)。修改后，原來的i值的個數就減少一個，而新i值的個數多一個。在程序中，用num數組來保存所有距離的個數，當把距離值從x修改為y時，num[x]–-,num[y]++即可，然后檢查num[x]是否為0，如果是0，那么s-t不連通，算法終止。原因顯而易見：比如s-t的距離是3，如果距離為2的情況都已經沒了，更別提走到距離為1的點了。這就是所謂的“gap優化”。 通過之前的分析，在數據結構方面，該算法只比Dinic算法的數據結構多了兩個數組：用于記錄父邊以便于撤退的數組p，以及標記距離個數的數組num。增廣的時候分為兩步，第一步逆推求出可改進量a（即殘余量的最小值）；第二步再逆推一遍，進行增廣。主過程中，x走到匯點時增廣。 在下面代碼中，由于我們是連續存的正向邊和反向邊，如0和1,2和3，等等。而他們分別與1異或后可以得到對方（二進制最后一位變反，其他位不變），所以我們在更新反向邊時用到了這一點。 代碼：
int source; // 源點int sink; // 匯點int p[max_nodes]; // 可增廣路上的上一條弧的編號int num[max_nodes]; // 和 t 的最短距離等于 i 的節點數量int cur[max_nodes]; // 當前弧下標int d[max_nodes]; // 殘量網絡中節點 i 到匯點 t 的最短距離bool visited[max_nodes];bool bfs(){ memset(visited, 0, sizeof(visited)); queue<int> Q; Q.push(sink);visited[sink] = 1;d[sink] = 0; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (iterator_t ix = G[u].begin(); ix != G[u].end(); ++ix) { Edge &e = edges[(*ix)^1]; if (!visited[e.from] && e.capacity > e.flow) visited[e.from] = true,d[e.from] = d[u] + 1,Q.push(e.from); } } return visited[source];}int augment(){ int u = sink, df = __inf;// 從匯點到源點通過 p 追蹤增廣路徑, df 為一路上最小的殘量 while (u != source) { Edge &e = edges[p[u]]; df = min(df, e.capacity - e.flow); u = edges[p[u]].from; } u = sink;// 從匯點到源點更新流量 while (u != source) { edges[p[u]].flow += df; edges[p[u]^1].flow -= df; u = edges[p[u]].from; } return df;}int max_flow(){ int flow = 0; bfs(); memset(num, 0, sizeof(num)); for (int i = 0; i < num_nodes; i++) num[d[i]]++; int u = source; memset(cur, 0, sizeof(cur)); while (d[source] < num_nodes) { if (u == sink) { flow += augment(); u = source; } bool advanced = false; for (int i = cur[u]; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if (e.capacity > e.flow && d[u] == d[e.to] + 1) { advanced = true; p[e.to] = G[u][i]; cur[u] = i; u = e.to; break; } } if (!advanced) { // retreat int m = num_nodes - 1; for (iterator_t ix = G[u].begin(); ix != G[u].end(); ++ix) if (edges[*ix].capacity > edges[*ix].flow) m = min(m, d[edges[*ix].to]); if (--num[d[u]] == 0) break; // gap 優化 num[d[u] = m+1]++; cur[u] = 0; if (u != source) u = edges[p[u]].from; } } return flow; }二：最小割 1：定義 割：流網絡圖G=(V,E)的一個劃分，記作[S,T]，將點集[V]劃分為S和T兩部分，且使得s屬于S，t屬于T，S+T=V。 最小割：一個網絡的最小割也就是該網絡中容量最小的割。 最大流最小割定理：流網絡圖G=(V,E)的最大流大小等于其最小割容量。 帶權圖的割就是割集中邊或者有向邊的權和 通俗的理解一下: 割集好比是一個恐怖分子 把你家和自來水廠之間的水管網絡砍斷了一些 然后自來水廠無論怎么放水 水都只能從水管斷口嘩嘩流走了 你家就停水了 割的大小應該是恐怖分子應該關心的事 畢竟細管子好割一些 而最小割花的力氣最小 下面介紹網絡流理論中一個最為重要的定理 最大流最小割定理:網絡的最大流等于最小割 具體的證明分三部分 1.任意一個流都小于等于任意一個割 由于容量限制 每一根的被砍的水管子流出的水流量都小于管子的容量 每一根被砍的水管的水本來都要到你家的 現在流到外面 加起來得到的流量還是等于原來的流 管子的容量加起來就是割 所以流小于等于割 由于上面的流和割都是任意構造的 所以任意一個流小于任意一個割
2.構造出一個流等于一個割 當達到最大流時 根據增廣路定理 殘留網絡中s到t已經沒有通路了 否則還能繼續增廣 我們把s能到的的點集設為S 不能到的點集為T 構造出一個割集C[S,T] S到T的邊必然滿流 否則就能繼續增廣 這些滿流邊的流量和就是當前的流即最大流 把這些滿流邊作為割 就構造出了一個和最大流相等的割
3.最大流等于最小割 設相等的流和割分別為Fm和Cm 則因為任意一個流小于等于任意一個割 任意F≤Fm=Cm≤任意C 定理說明完成
所以，我們就可以把最小割轉化為最大流，使用上面介紹的三種算法。
三:最大權閉合圖、最大密度子圖、混合圖歐拉回路
最大權閉合圖：（此部分轉載） 這里閉合圖的概念就很好引出了。在一個圖中，我們選取一些點構成集合，記為V，且集合中的出邊(即集合中的點的向外連出的弧)，所指向的終點(弧頭)也在V中，則我們稱V為閉合圖。最大權閉合圖即在所有閉合圖中，集合中點的權值之和最大的V，我們稱V為最大權閉合圖。 
上圖中閉合圖有
最大權閉合圖為{3,4,5}。
針對本題而言，我們將實驗與儀器間連一條有向邊，實驗為起點(弧尾)，儀器為終點(弧頭)。則如果我們選擇一個閉合圖，那么這個閉合圖中包含的實驗所需要的儀器也最這個閉合圖里。而最大權閉合圖即為題目的解。
了解了最大權閉合圖的概念，接下來我們就需要知道如何求最大權閉合圖。
首先我們將其轉化為一個網絡(現在不要問為什么,接下來會證明用網絡可以求解)。構造一個源點S，匯點T。我們將S與所有權值為正的點連一條容量為其權值的邊，將所有權值為負的點與T連一條容量為其權值的絕對值的邊，原來的邊將其容量定為正無窮。
上圖即被轉化為如左圖網絡。
首先引入結論，最小割所產生的兩個集合中，其源點S所在集合(除去S)為最大權閉合圖，接下來我們來說明一些結論。
證明:最小割為簡單割。 1：引入一下簡單割的概念：割集的每條邊都與S或T關聯。(請下面閱讀時一定分清最小割與簡單割，容易混淆):那么為什么最小割是簡單割呢？因為除S和T之外的點間的邊的容量是正無窮，最小割的容量不可能為正無窮。所以，得證。
2：證明網絡中的簡單割與原圖中閉合圖存在一一對應的關系。(即所有閉合圖都是簡單割，簡單割也必定是一個閉合圖)。 證明閉合圖是簡單割：如果閉合圖不是簡單割(反證法)。那么說明有一條邊是容量為正無窮的邊，則說明閉合圖中有一條出邊的終點不在閉合圖中，矛盾。 證明簡單割是閉合圖：因為簡單割不含正無窮的邊，所以不含有連向另一個集合(除T)的點，所以其出邊的終點都在簡單割中，滿足閉合圖定義。得正。 3：證明最小割所產生的兩個集合中，其源點S所在集合(除去S)為最大權閉合圖。 首先我們記一個簡單割的容量為C,且S所在集合為N，T所在集合為M。 則C=M中所有權值為正的點的權值(即S與M中點相連的邊的容量)+N中所有權值為負的點權值的絕對值(即N中點與T中點相連邊的容量)。記(C=x1+y1);(很好理解，不理解畫一個圖或想象一下就明白了)。 我們記N這個閉合圖的權值和為W。 則W=N中權值為正的點的權值-N中權值為負的點的權值的絕對值。記(W=x2-y2); 則W+C=x1+y1+x2-y2。 因為明顯y1=y2，所以W+C=x1+x2; x1為M中所有權值為正的點的權值，x2為N中權值為正的點的權值。 所以x1+x2=所有權值為正的點的權值之和(記為TOT). 所以我們得到W+C=TOT.整理一下W=TOT-C. 到這里我們就得到了閉合圖的權值與簡單割的容量的關系。 因為TOT為定值，所以我們欲使W最大，即C最小，即此時這個簡單割為最小割，此時閉合圖為其源點S所在集合(除去S)。得正。 至此，我們就將最大權閉合圖問題轉化為了求最小割的問題。求最小割用最小割容量=最大流，即可將問題轉化為求最大流的問題。 【持續更新中…】
新聞熱點
疑難解答
