網路最大流的標號演算法

1. 構造輔助網路後如何用最大流演算法求最小割

在演算法中一般存在最大-最小定理。

1 、最大匹配<==>最小覆蓋

2、 最大流<==>最小割

最大流-最小割定理理解引自呆歐的形象表達：「多粗的管子，水就最多多大流量」，比如從自來水廠到用水大戶工業小區A 能達到的水的最大流量是多大？考慮到可能從水廠到小區有不少到達的水管，那麼最大的流量等於拆掉最少最細的水管後水廠不能給小區A 供水的那些水管流量的集合。當然這種說法並不不嚴謹，因為這里水管不是雙向的，而在網路中談論的信息流卻可是是雙向的。

其實最大流-最小割最難的地方在於構圖了，還有必須掌握Dinic演算法。

高效的求最大流演算法——Dinci演算法：

Dinci演算法是基於「層次圖」的時間效率優先的最大流演算法。

層次：從源點走到終點的最短路長度。層次圖：每次從源點到終點距離最短並且記錄了多條增廣路徑（在找到最短路的過程記錄了多條增廣路徑，因為找最短路徑的過程中自然有分叉，有分叉那麼增廣路徑條數不就變多了么）。在dfs遍歷的時候必須按照層次走。

Dinic演算法的思想是為了減少增廣次數，建立一個輔助網路L，L與原網路G具有相同的節點數，但邊上的容量有所不同，在L上進行增廣，將增廣後的流值回寫到原網路上，再建立當前網路的輔助網路，如此反復，達到最大流

Dinic三步曲：

1、利用原網路構造層次圖，順便判斷原網路還有無增廣路。

2、利用構造的層次圖求此次的最大流，若找不到增廣路了則演算法結束

3、更新原網路，即增廣過程中遇見的邊其正邊以及逆邊的的容量大小。

重復上述的三步。

2. 怎麼樣求網路的最大流和最小截集

首先是網路流中的一些定義：
V表示整個圖中的所有結點的集合.
E表示整個圖中所有邊的集合.
G = (V,E) ,表示整個圖.
s表示網路的源點,t表示網路的匯點.
對於每條邊(u,v),有一個容量c(u,v) (c(u,v)>=0)，如果c(u,v)=0，則表示(u,v)不存在在網路中。相反，如果原網路中不存在邊(u,v)，則令c(u,v)=0.
對於每條邊(u,v),有一個流量f(u,v).

一個簡單的例子.網路可以被想像成一些輸水的管道.括弧內右邊的數字表示管道的容量c,左邊的數字表示這條管道的當前流量f.

網路流的三個性質：
1、容量限制: f[u,v]<=c[u,v]
2、反對稱性：f[u,v] = - f[v,u]
3、流量平衡: 對於不是源點也不是匯點的任意結點,流入該結點的流量和等於流出該結點的流量和。
只要滿足這三個性質,就是一個合法的網路流.
最大流問題，就是求在滿足網路流性質的情況下，源點 s 到匯點 t 的最大流量。

求一個網路流的最大流有很多演算法 這里首先介紹 增廣路演算法（EK）
學習演算法之前首先看了解這個演算法中涉及到的幾個圖中的定義：

**殘量網路
為了更方便演算法的實現，一般根據原網路定義一個殘量網路。其中r(u,v)為殘量網路的容量。
r(u,v) = c(u,v) – f(u,v)
通俗地講：就是對於某一條邊（也稱弧），還能再有多少流量經過。
Gf 殘量網路,Ef 表示殘量網路的邊集.

這是上面圖的一個殘量網路。殘量網路（如果網路中一條邊的容量為0,則認為這條邊不在殘量網路中。
r(s,v1)=0,所以就不畫出來了。另外舉個例子：r(v1,s) = c(v1,s) – f(v1,s) = 0 – (-f(s,v1)) = f(s,v1) = 4.
其中像(v1,s)這樣的邊稱為後向弧,它表示從v1到s還可以增加4單位的流量。
但是從v1到s不是和原網路中的弧的方向相反嗎？顯然「從v1到s還可以增加4單位流量」這條信息毫無意義。那麼，有必要建立這些後向弧嗎？
顯然，第1個圖中的畫出來的不是一個最大流。
但是，如果我們把s -> v2 -> v1 -> t這條路徑經過的弧的流量都增加2,就得到了該網路的最大流。
注意到這條路徑經過了一條後向弧:(v2,v1)。
如果不設立後向弧，演算法就不能發現這條路徑。
**從本質上說，後向弧為演算法糾正自己所犯的錯誤提供了可能性，它允許演算法取消先前的錯誤的行為（讓2單位的流從v1流到v2)

注意,後向弧只是概念上的,在程序中後向弧與前向弧並無區別.

**增廣路
增廣路定義：在殘量網路中的一條從s通往t的路徑，其中任意一條弧(u,v)，都有r[u,v]>0。

如圖綠色的即為一條增廣路。

看了這么多概念相信大家對增廣路演算法已經有大概的思路了吧。

**增廣路演算法
增廣路演算法：每次用BFS找一條最短的增廣路徑，然後沿著這條路徑修改流量值（實際修改的是殘量網路的邊權）。當沒有增廣路時，演算法停止，此時的流就是最大流。

**增廣路演算法的效率
設n = |V|, m = |E|
每次增廣都是一次BFS,效率為O(m),而在最壞的情況下需要（n-2增廣。（即除源點和匯點外其他點都沒有連通，所有點都只和s與t連通）
所以,總共的時間復雜度為O(m*n)，所以在稀疏圖中效率還是比較高的。

hdoj 1532是一道可以作為模板題目練手。
模板代碼：

[cpp] view plain print?
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int N = 1100;
const int INF = 0x3f3f3f3f;

struct Node
{
int to;//終點
int cap; //容量
int rev; //反向邊
};

vector<Node> v[N];
bool used[N];

void add_Node(int from,int to,int cap) //重邊情況不影響
{
v[from].push_back((Node){to,cap,v[to].size()});
v[to].push_back((Node){from,0,v[from].size()-1});
}

int dfs(int s,int t,int f)
{
if(s==t)
return f;
used[s]=true;
for(int i=0;i<v[s].size();i++)
{
Node tmp = v[s][i]; //注意
if(used[tmp.to]==false tmp.cap>0)
{
int d=dfs(tmp.to,t,min(f,tmp.cap));
if(d>0)
{
tmp.cap-=d;
v[tmp.to][tmp.rev].cap+=d;
return d;
}
}
}
return 0;
}

int max_flow(int s,int t)
{
int flow=0;
for(;;){
memset(used,false,sizeof(used));
int f=dfs(s,t,INF);
if(f==0)
return flow;
flow+=f;
}
}
int main()
{
int n,m;
while(~scanf("%d%d",n,m))
{
memset(v,0,sizeof(v));
for(int i=0;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",x,y,z);
add_Node(x,y,z);
}
printf("%d\n",max_flow(1,m));
}
}