网络流（Network-Flow )
主要内容
最大流算法
最小费用流算法
网络流算法应用举例
皇家空军飞行员问题
最小逃脱问题
最佳航空路线问题
背景
许多系统包含了流量问题。
例如： 公路系统中有车辆流，
控制系统有信息流，
供水系统中有水流，
金融系统中有现金流等。
图为连接产地V1和销地V7的交通网,边上 的数字表示这条边的最大通过量Cij(容量),括号里的数字表示实际通过量fij(流量)。
所有括号里的数fij (i=1,…,7)给出一种
运输方案。
例1
网络与流
网络
G=(V,E) ,V={1,2,…,n}是一个简单有向图.V中有一顶点s称为源，另一顶点t称为汇。对于有向图G的每条边(i,j)∈E,对应有一个值capa(i,j)≥0,称为边的容量。 这种有向图G称作一个网络，记为G=(V,E,capa)。
网络与流
流量（flow)
对于给定的网络G, 从源点出来的“货物”, 经过网络上的有向边, 最后流入汇点的“货物”称为流量, 而每一条边( vi vj ) 流过的流量,记为f ( vi vj ) (或f ( i j) )称为边( vi vj ) 的流。
网络与流
流量（flow)
对给定的网络G, 若每条边上的流都知道, 即相当于在G 的边集E上定义了一个函数(即G上所有边的流的全体)
F = { f ( vi vj) | vi , vj ∈ V }
则称F 是网络G 的流。
汇
源
流
s
2
3
4
5
6
7
t
0
0
0
0
4
4
0
0
0
0
4
0
0
4
0
显然,边( vi vj ) 的流不能超过该边的容量 , 因此有0 ≤ f ( ( vi vj ) ≤ c (vi vj )
满足上式的网络称为相容网络。
网络与流
可行流
满足以下条件的流f称为可行流：
容量限制：对每条边(i,j)∈E,
0≤f(i,j) ≤capa(i,j);
平衡条件：
对中间点i：
对源s:
对汇t:
-
-
净输出量
净输入量
s
2
3
4
5
6
7
t
4/10
0/9
0/10
0/15
0/30
0/ 6
0/10
0/5
4/8
4/10
0/15
4/10
0/15
0/15
0/4
容量
流量
|f|为可行流f的流量
|f|=4
最大流问题
给一流网络G，源 s以及汇t。求一个网络的流{f(i,j)},使其流量|f|达到最大且是可行流。
最大流问题
12/12
s
v1
v3
v2
v4
t
f(u,v)/c(u,v)
11/16
8/13
0/10
1/4
11/14
4/9
7/7
15/20
4/4
饱和边：
网络中满足f(i,j)=capa(i,j)的边(i,j)称为饱和边。
非饱和边：如果f(i,j)<capa(i,j)，则称(i,j)为非饱和边
例：P11的网络流中有非饱和边：
（s,2)(s,3)(s,4)…
最大流问题
零流边与非零流边：
f(i,j)=0的边称为零流边,f(i,j)>0的边称为非零流边
例P11的网络流(s,3)(s,4)(2,5)(2,6)(7,3)…是零流边
最大流问题
前向边与后向边：
网络中的任一条与路方向一致的边(i,j) 称为前向边P+ ；
定义前向边的可改进量为capa(i,j)-f(i,j)。
例： P11的“红色”的通路中， (S,3),(7,t）是前向边
相应的与路方向相反的边(j,i)称为后向边P-
定义后向边的可改进量为f(j,i)。
例： P11的“红色”的通路中， (7,3）是后向边
最大流问题
前向边和后向边
12/12
s
v1
v3
v2
v4
t
f(u,v)/c(u,v)
11/16
8/13
0/10
1/4
11/14
4/9
7/7
15/20
4/4
路径P:{s,v1,v3,v4,t}中，边（v3,v4）是后向边，其余为前向边。
后向边（V1,V3）的可改进量是7
前向边(s,v1)的可改进量是16-11=5
可改进路（增广路， Augmenting Path)
对于源s到汇t的一条简单路，如果路上的每条边(i,j)的可改进量均大于0,则称这条路为一条可改进路(增广路)。
所有边的可改进量的最小值为可改进路的改进量
图(a)(b) 的可改进路P(V1,V3,V2,V4,V6).
调整该路径的流量
确定改进量a:
先看P+={(V1,V2),(V2,V4),(V4,V6)}
c(1,3)-f(1,3)=8-2=6
c(2,4)-f(2,4)=4-0=4
c(4,6)-f(4,6)=7-2=5
再看P的后向边集合p-={(V2,V3)}, f(2,3)=2
因此改进量a至多取2。使改进后的前向边流量增加，又使改进后的后向边的流量不为负。
改进后流量增为2。
改进后的网络流量
沿P(V1V2V4V6）改进后的网络流量
引入增广路：
增广路定理：
网络达到最大流当且仅当不存在可改进路（增广路）。
如果网络中有一条可改进量为k的增广路，则沿着它改进（所有前向边流量增加k,所有后向边的流量减少k)以后流仍然是可行的，且网络流量增加k。
求解最大流
寻找增广路
设f是一个可行流，p是从s到t的一条路，若：
在p的所有前向边(i,j)上，0≤f(i,j)<capa(i,j).
非饱和边 改进量为a=capa(i,j)-f(i,j)。
(2) 在p的所有后向边(i,j)上，0<f(i,j)≤capa(i,j).
非零流边 改进量为a=f(i,j)。
则称P为关于可行流f的一条增广路。
所有边的可改进量的最小值为增广路p的改进量
按下面的公式修改当前的流:
为寻找增广路，可定义剩余网络，剩余网络中存在从源到汇的路径，则这条路径就是增广路。
流的剩余网络与原始流网络G有相同顶点，原始网络每条边（i，j)在剩余网络中对应一条或两条边：
令（i，j)的流量为f,容量为c。
（1）若(i,j)是不饱和边，f<c,则剩余网络中包含边（i，j),其容量为c-f
（2）若(i,j)是非零流边，f>0,则剩余网络中包含边（j，i),其容量为f
最大流增广路算法(Ford Fulkerson)
设f是网络G的一个可行流，如果不存在从s到t关于f的可改进路p，则f一定是最大流。
增广路方法：
（1）置f=0为初始可行流；
（2）while (存在从s到t关于f的可改进路）do
begin
找出一条从s到t关于f的可改进路p;
计算关于f的可改进路p的可改进量a;
根据可改进量a改进当前可行流的流量
end;
Ford-Fulkerson 最大流
4
1
1
2
2
1
2
3
3
1
s
2
4
5
3
t
这是初始网络以及初始剩余网络.
剩余网络N中任何一条从s到t的路径都是增广路
4
1
1
2
2
1
2
3
3
1
在G(x)中寻找任何s-t 路径.
s
2
4
5
3
t
4
1
1
2
1
3
判定路径的可改经量a.
在路径上发送 a单位的流.
更新剩余容量.
1
1
1
2
1
2
3
2
1
s
2
4
5
3
t
4
1
1
2
1
3
寻找任何s-t 路径
1
1
1
2
1
2
3
2
1
s
2
4
5
3
t
4
2
1
1
1
1
2
2
1
1
1
1
3
1
1
1
1
3
2
1
s
2
4
5
3
t
判定路径的可改进量 a
在路径中发送 a 单位的流.
更新剩余网络
4
2
1
1
1
1
2
2
1
1
1
1
3
1
1
1
1
3
2
1
s
2
4
5
3
t
寻找任何 s-t 路径
1
1
1
1
1
4
1
2
1
1
2
1
1
3
1
1
3
2
1
s
2
4
5
3
t
判定路径的可改进量 a
在路径中发送 a单位的流.
更新剩余网络
1
1
1
1
1
4
1
2
1
1
2
2
1
1
3
1
1
3
2
1
s
2
4
5
3
t
寻找任何 s-t 路径
1
1
1
2
1
1
1
1
4
2
2
1
1
2
2
1
1
1
3
1
1
s
2
4
5
3
t
2
判定路径的可改进量 a
在路径中发送 a 单位的流.
更新剩余网络
1
1
2
1
1
1
1
4
2
2
1
1
2
2
1
1
1
3
1
1
s
2
4
5
3
t
寻找任何 s-t 路径
2
1
1
1
1
1
4
1
3
1
1
2
1
1
3
2
2
1
2
1
2
1
s
2
4
5
3
t
2
判定路径的可改进量 a
在路径中发送 a单位的流.
更新剩余网络
1
1
1
1
1
4
1
3
1
1
2
1
1
3
2
2
1
2
1
2
1
s
2
4
5
3
t
2
在剩余网络中没有 s-t 路径.
此流是最优的.
1
1
1
1
1
4
1
3
1
1
2
1
1
3
2
2
1
2
1
2
1
s
2
4
5
3
t
2
这些是从结点 s 可达的结点.
最小截量=5 V1={s,2,3,4,5},V2={t}
s
2
4
5
3
1
1
2
2
2
1
2
s
2
4
5
3
t
这是最优流.
Ford-Fulkerson 最大流
最短增广路法
4
1
1
2
2
1
2
3
3
1
s
2
4
5
3
t
这是初始网络以及初始剩余网络.
寻找最短增广路
1
4
1
1
2
2
1
2
3
3
1
宽度优先搜索，标号节点距离
s
2
4
5
3
t
0
1
1
2
2
1
4
1
1
2
2
1
2
3
3
1
选取2条最短增广路中的任一条
s
2
4
5
3
t
0
1
1
2
2
4
2
2
2
1
3
判定路径的可改经量a=2.
在路径上发送 a单位的流.
更新剩余容量.
1
1
2
1
2
3
1
1
s
2
4
5
3
t
1
0
1
2
2
2
4
2
2
2
1
3
寻找最短 路径
1
1
2
1
2
3
1
1
s
2
4
5
3
t
1
0
1
2
2
2
4
2
2
1
3
在路径上发送 a单位的流.
更新剩余容量.
1
1
2
1
3
1
1
s
2
4
5
3
t
1
0
2
3
2
3
4
4
2
2
1
3
1
1
2
1
3
1
1
s
2
4
5
3
t
1
0
2
3
2
3
4
寻找最短路径
3
2
2
1
3
1
1
2
1
2
1
1
s
2
4
5
3
t
0
2
1
1
1
在路径上发送 a单位的流.
更新剩余容量.
无法标号，算法结束
1
1
1
1
1
4
1
3
1
1
2
1
1
3
2
2
1
2
1
2
1
s
2
4
5
3
t
2
这些是在剩余网络中从结点 s 可达的结点.
最小截量=5 V1={s,2,3,4,5},V2={t}
s
2
4
5
3
1
1
2
2
2
1
2
s
2
4
5
3
t
这是最优流. （最短增广路只用三条增广路就得到最大流）
例: 赛车问题
阿P与阿Q都是赛车好手，他们各有N辆赛车。为了一比高下，他们约好进行一场比赛。
这次比赛共有M个分站赛，赢得分站赛场次多的获得总冠军。
每个分站赛中，两人各选一辆自己的赛车比赛。分站赛的胜负大部分取决于两车的性能，但由于种种原因（如相互之间的干扰），性能并不是决定胜负的唯一指标，有时会出现A赢B、B赢C、C赢D、D又赢A的局面。幸好有一种高智能机器，只要给定两辆赛车，就能立刻判断谁会赢，在总比赛前它就已经把阿p的每辆车与阿q的每辆车都两两测试过了，并且还把输赢表输入了电脑。
另外，由于比赛的磨损，每辆赛车都有自己的寿命（即它们能参加分站赛的场次），不同的赛车寿命可能不同，但最多不会超过50场。两辆赛车最多只能交手一次。
现给定N、M（1<=N<=100，1<=M<=1000）、N*N的一个输赢表、每辆赛车的寿命，并假设每次分站赛两人都有可选的赛车，请你计算一下阿P最多能够赢得多少个分站赛。
例: 赛车问题-构图
1、建立N个点代表阿P的N辆车，分别以1到N标号；
2、建立N个点代表阿Q的N辆车，分别以N+1到2N标号；
3、如果阿P的第I辆车能够跑赢阿Q的第J辆车，则加一条弧IN+J，容量为1，表示两辆赛车最多只能交手一次；
4、增加一个源点S，S与 1到N中的每一个结点I都连一条弧SI，容量为阿P的第I辆车的寿命；
5、增加一个汇点T，N+1到2N中的每一个结点N+J到T都连一条弧N+JT，容量为阿Q的第J辆车的寿命；
6、再增加一个源点S2，加一条弧S2S，容量为M，表示最多M场分站赛 。
该网络的最大流就是P最多能赢多少场比赛。
最小费用流问题
与网络流有关的问题：
流量
费用
网络中的每条边定义了：
容量capa(i,j)
单位流量费用cost(i,j)
最小费用流问题
最小费用流问题描述如下：
对给定的流量F，求一个最小费用流f，使流的总输送费用最小。
cost(f)=
最小费用流问题
如何求最小费用流？
分析：
设p是关于可行流f的一条可改进路，以a=1调整f,得到新的可行流费用的变化情况。
cost(f)-cost(f)=
=
a=1
a=1
-
可行路p的费用
最小费用流问题
如何求最小费用流？
分析：
设p是关于可行流f的一条可改进路，以a=1调整f,得到新的可行流费用的变化情况。
cost(f)-cost(f)=
-
可行路p的费用
P是单位流量费用最小的可改进路，沿p调整
得到所有可改进路中最小费用流
最小费用流问题
如何求最小费用流？
寻找费用最小的可改进路p
沿p调整可改进路得到最小费用流
算法
算法实现
最小费用流问题
如何寻找费用最小的可改进路p ？
方法：
构造带权有向图w(f)。G中的每条边变成两个方向相反的边(i,j)和(j,i)。
w(i,j)= cost(i,j) f(i,j)<c(i,j) 不饱和边
+∞ f(i,j)=c(i,j) 饱和边
w(j,i)= -cost(i,j) f(i,j>0 非零流边
+∞ f(i,j)=0 零流边
（长度为∞的可以从w(f)中略去）
w(f)中路径p上的各边权之和即为原图G中相应可改
进路P的费用。
w(f)的最短路即为G中的最小费用可改进路。
-
可行路p的费用
return
最小费用流问题
算法：
（0）f=0为初始可行流
（1）设f是当前可行流。|f|=F时，已找到最小费用流，算法结束，否则转①。
① 构造带权有向图w(f).在w(f)中寻找最短路
② 若不存在最短路，则f为最小费用最大流；若存在最短路，则得到G中相应的可改进路p，调整p：
a=min{minP+{capa(i,j)-f(i,j)},minp-{f(i,j),F-|f|}
f(i,j)+a (i,j)∈p+
f(i,j)= f(i,j)-a (i,j)∈p-
f(i,j) (i,j)不属于p
得到新的可行流f,再对f重复上述步骤（1）。
return
最小费用流问题
主要函数：
locate和wlocate :确定边(i,j)在邻接表adj（图G）
和wadj(图w(f))中的位置。
constructw: 初始化附加网络w(f)
changew: 根据当前可行流重构附加网络w(f)
computea: 根据当前可改进路计算网络流的可改进量a
found: 找当前附加网络w(f)的最短路（即当前可行流
的最小费用可路）及可改进流量a
change: 根据可改进流量a调整当前可行流
最小费用流算法Mincost: procedure Mincost;
var a:integer;
begin
current:=0;
while found(a) do change(a);
end
最小费用流问题
function locate(i,j:integer):pointer;
var p:pointer;
begin
p:=adj[i];
while (p<>nil) and (p^.v<>j) do
p:=p^.next;
locate:=p;
end;
return
最小费用流问题
function wlocate(i,j,k:integer):wpointer;
{k=1表示向前边，k=-1表示向后边}
var p:pointer;
begin
p:=wadj[i];
if (k>0) then
while (p<>nil) and (p^.v<>j) do
p:=p^.next;
else
while (p<>nil) and (p^.v<>-j) do
p:=p^.next;
wlocate:=p;
end;
return
最小费用流问题
procedure constructw;
var p:pointer;
q:wpointer;
begin
for i:=q to n do
wadj[i]:=nil;
for i:=1 to n do
begin
p:=adj[i];
while (p<>nil) do
begin
j:=p^.v;
new(q);
q^.v:=j;
q^.w:=maxint;
q^.next:=wadj[i];
wadj[i]:=q;
new(q);
q^.v:=-I;
q^.w:=maxint;
q^.next:=wadj[j];
wadj[j]:=q;
p:=q^.next;
end;
end;
end;
return
最小费用流问题
procedure changew;
var i:integer;
p:pointer;
q:wpointer;
begin
for i:=1 to n do
begin
q:=wadj[i];//W(f)中i的邻接点
while (q<>nil) do
begin
q^.w:=maxint;
q:=q^.next;
end;
end;
for i:=1 to n do
begin
p:=adj[i];
while (p<>nil) do
begin
if (p^.capa>0) then
begin
非饱和边 if p^.flow<p^.capa then
begin
q:=wlocate(I,p^.v,1);
q^.w=p^.cost;
end;
非零流边 if (p^.flow>0) then
begin
q:=wlocate(p^.v,i,-1);
q^.w:=-p^.cost;
end;
end;
P:=p^.next;
end;
end;
end;
return
最小费用流问题
procedure computea:integer;
var a,j,k,x:integer;
p,q:pointer;
begin
k:=t;
a:=maxint;
While k<>s do
begin
j:=k;
k:=abs(prev[j]);
p:=locate(j,k);
q:=locate(k,j);
if (prev[j]<0) and (p<>nil) then x:=p^.flow;
if (prev[j]>0) and (q<>nil) then x:=p^.capa-q^.flow;
if a>x then a:=x
end;
if a>f-current then a:=f-current;
computea:=a;
end;
向后边
前向边
return
最小费用流问题
procedure found(var a:integer):boolean;
begin
found:=false;
if (f=current) then exit;
changew;
if (not shortpath(s,t)) then exit;
found:=true;
a:=computea;
end;
return
最小费用流问题
procedure change(a:integer);
var i，j:integer;
p,q:pointer;
begin
j:=t;
while j<>s do
begin
i:=j;
j:=abs(prev[i]);
p:=locate(i,j);
q:=locate(j,i);
if (p<>nil) and (prev[i]<0) then p^.flow:=p^.flow-a;
if (q<>nil) and (prev[i]>0) then q^.flow:=q^.flow+a;
end;
current:=current+a;//当前网络流量
end;
return
开始取f(0)=0,一般若在第k-1步得到最小费用流f(k-1),则构造带权有向图W(f(k-1)),在W(f(k-1))中寻找从Vs到Vt的最短路。
若不存在最短路，则f(k-1)即最小费用最大流。
若存在最短路，则该最短路就是原网络G中的可改进路P,在可改进路P上对f(k-1)进行调整（计算路径的可改进量a,对前向边的流量加上a,后向边的流量减去a)。
得到新的可行流F(k),在对F(k)重复上述步骤。
例：求最小费用最大流
（1） 取F(0)=0为初始可行流
（2） 构造带权有向图W(F(0)),并求出从Vs到Vt的最短路(Vs,V2,V1,Vt).如图(a)(双箭头为最短路）
（3） 原网络G中，与这条最短路相应的可改进路为P=(Vs,v2,v1,vt)
（4） 在P上进行调整，得a=5 ,得F(1).如图b
（5） 按上述算法依次得到F(2),F(3),F(4)的流量为7，10，11（b,d,f,h)；构造的赋权有向图为W(F(1)),W(F(2)),W(F(3)),W(F(4))(c,e,g,i)
（6） W(F(4))中不存在从Vs到Vt的最短路径，因此F(4)就是最小费用最大流。
最小费用最大流 应用
问题1-最小运输费用：
假设有N个经销商和M个供应地，每个供应地提供k种不同商品。一旦经销商订购商品，就应该安排各供应地为经销商供货并且尽可能降低总运输成本。
来自不同地点供给不同经销商的不同商品的运输成本可能不同。已知K种商品的每种供应地，N个经销商订单情况以及相应的运输成本，该如何安排商品运输使运输费用最小。
Input
1 3 3 //经销商个数，供应地个数，商品个数
N=1，M=3，K=3
1 1 1 //经销商需要的各种商品的数量。
0 1 1 //供应地1商品库存
1 2 2 //供应地2商品库存
1 0 1 //供应地3商品库存
1 2 3 //商品1的运输单价
1 1 1 //商品2的运输单价
2 1 1 //商品3的运输单价
Output
4
最小费用最大流 应用
问题2-小人与房子：
网格图上n个小人和n个房子。在单位时间内，每个小人可沿横向或纵向移动一步到达相邻点。对每一个小人，他每移动一步需要你支付1美元的费用，直到他进入一所房子。任务条件是每个房子只可容纳一个小人。
计算将n个小人移到n个房间所需的最低费用。
实际是二部图匹配问题
Input
2 2 //地图的行列数
.m //第1行第2列有1人
H. //第2行第1列有1房子
5 5 //5*5
HH..m //房子，房子，空，空，人
.....
.....
.....
mm..H
Output
2
10
网络流算法应用举例
皇家飞行员问题
问题描述
二战期间，英国皇家空军从沦陷国征募大量外籍飞行员。由皇家空军派出的每架飞机需配备：
两名飞行员（1名英国飞行员，1名外籍飞行员）
每名外籍飞行员可与若干英国飞行员配合
如何为飞行员配对，使一次派出最多飞机。
网络流算法应用举例
皇家飞行员问题
输入文件 输出文件
10 10 总数n 配合数e 4 派出飞机数
1 7 （外籍i,英国j) 1 7 配对方案
1 8 2 6
2 6 4 8
2 9 5 10
2 10
3 7
3 8
4 7
4 8
5 10
1
2
3
4
5
6
7
8
9
10
网络流算法应用举例
皇家飞行员问题
输入文件 输出文件
10 10 总数n 配合数e 4 派出飞机数
1 7 （外籍i,英国j) 1 7 配对方案
1 8 2 6
2 6 4 8
2 9 5 10
2 10
3 7
3 8
4 7
4 8
5 10
1
2
3
4
5
6
7
8
9
10
网络流算法应用举例
皇家飞行员问题
输入文件 输出文件
10 10 总数n 配合数e 4 派出飞机数
1 7 （外籍i,英国j) 1 7 配对方案
1 8 2 6
2 6 4 8
2 9 5 10
2 10
3 7
3 8
4 7
4 8
5 10
1
2
3
4
5
6
7
8
9
10
网络流算法应用举例
皇家飞行员问题
输入文件 输出文件
10 10 总数n 配合数e 4 派出飞机数
1 7 （外籍i,英国j) 1 7 配对方案
1 8 2 6
2 6 4 8
2 9 5 10
2 10
3 7
3 8
4 7
4 8
5 10
1
2
3
4
5
6
7
8
9
10
网络流算法应用举例
皇家飞行员问题
输入文件 输出文件
10 10 总数n 配合数e 4 派出飞机数
1 7 （外籍i,英国j) 1 7 配对方案
1 8 2 6
2 6 4 8
2 9 5 10
2 10
3 7
3 8
4 7
4 8
5 10
1
2
3
4
5
6
7
8
9
10
网络流算法应用举例
皇家飞行员问题
输入文件 输出文件
10 10 总数n 配合数e 4 派出飞机数
1 7 （外籍i,英国j) 1 7 配对方案
1 8 2 6
2 6 4 8
2 9 5 10
2 10
3 7
3 8
4 7
4 8
5 10
1
2
3
4
5
6
7
8
9
10
网络流算法应用举例
皇家飞行员问题
解题思路
二分图的最大匹配问题。
转换为网络最大流问题。
1
2
3
4
5
6
7
8
9
10
X
Y
二分图G
(1)
网络流算法应用举例
皇家飞行员问题
解题思路
二分图的最大基数匹配问题。
转换为网络最大流问题。
s
1
2
3
4
5
6
7
8
9
10
t
X
Y
(2)
网络流算法应用举例
皇家飞行员问题
解题思路
二分图的最大基数匹配问题。
转换为网络最大流问题。
s
1
2
3
4
5
6
7
8
9
10
t
X
Y
(3)
网络流算法应用举例
皇家飞行员问题
解题思路
二分图的最大基数匹配问题。
转换为网络最大流问题。
求网络H的最大流f
最大流值|f|对应二分图G的
最大匹配边数。
s
1
2
3
4
5
6
7
8
9
10
t
X
Y
网络图H
(4)
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
网络流算法应用举例
皇家飞行员问题
解题思路
二分图的最大基数匹配问题。
转换为网络最大流问题。
求网络H的最大流f
最大流值|f|对应二分图G的
最大匹配边数。
s
1
2
3
4
5
6
7
8
9
10
t
X
Y
1
1/1
1
1
1
1/1
1
1
1
1
1
1
1
1
1
1/1
1
1
1
1
网络流算法应用举例
皇家飞行员问题
解题思路
二分图的最大匹配问题。
转换为网络最大流问题。
求网络H的最大流f,
存在可改进路则还有匹配。
s
1
2
3
4
5
6
7
8
9
10
t
X
Y
1/1
1/1
1
1
1
1/1
1/1
1
1
1
1
1
1
1
1
1/1
1/1
1
1
1
网络流算法应用举例
皇家飞行员问题
解题思路
二分图的最大基数匹配问题。
转换为网络最大流问题。
求网络H的最大流f
s
1
2
3
4
5
6
7
8
9
10
t
X
Y
1/1
1/1
1/1
1
1
1/1
1/1
1
1
1
1/1
1
1
1
1
1/1
1/1
1/1
1
1
网络流算法应用举例
皇家飞行员问题
解题思路
二分图的最大基数匹配问题。
转换为网络最大流问题。
求网络H的最大流f
s
1
2
3
4
5
6
7
8
9
10
t
X
Y
1/1
1/1
1/1
1
1/1
1/1
1/1
1
1
1
1/1
1
1
1/1
1
1/1
1/1
1/1
1
1/1
网络流算法应用举例
皇家飞行员问题
解题思路
最大流值|f|对应二分图G的
最大匹配边数。
s
1
2
3
4
5
6
7
8
9
10
t
1/1
1/1
1/1
1
1/1
1/1
1/1
1
1
1
1/1
1
1
1/1
1
1/1
1/1
1/1
1
1/1
|f|=4
网络流算法应用举例
皇家飞行员问题
解题思路
二分图的最大基数匹配问题。
1
2
3
4
5
6
7
8
9
10
网络流算法应用举例
最小逃脱问题
问题描述
m×n栅格无向图
ff个起始点(x1,y1),…,(xf,yf)
求从ff个起始点到边界点的ff条不相交路径。
存在则有逃脱，路径总长最小是最小逃脱
有逃脱
（13）
没有逃脱
最小逃脱
（11）
网络流算法应用举例
最小逃脱问题
输入文件 输出文件
6 6 10
6×6网格，10个起始点 11 路径总长度
2 2 起始点坐标 （2，2）（1，2）路径1
2 4 （2，3）（1，3）
2 6 （2，4）（1，4）
3 1 （2，5）（1，5）
3 2 （3，2）（3，3）
3 4 （3，3）（2，3）
3 6 （3，4）（3，5）
4 2 （3，5）（2，5）
4 4 （4，2）（4，1）
4 6 （4，4）（5，4）
（5，4）（6，4）
i=1或i=6或j=1或j=6，（i,j)是边界点
网络流算法应用举例
最小逃脱问题
解题思路
将m×n栅格→费用流网络
方法：
（1）将每个栅格点(i,j)拆成v（i,j,1)和v(i,j,2)
cap=1
cost=0
V(I,j,1)
V(I,j,2)
网络流算法应用举例
最小逃脱问题
解题思路
将m×n栅格→费用流网络
方法：
（1）将每个栅格点(i,j)拆成v（i,j,1)和v(i,j,2)
（2）（i,j)的4个邻点变为8个顶点
cap=1
cost=0
V(I,j,1)
V(I,j,2)
V(i-1,j,2)
V(i+1,j,2)
V(i,j-1,2)
V(i,j+1,2)
V(i-1,j,1)
V(i+1,j,1)
V(i,j-1,1)
V(i,j+1,1)
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
网络流算法应用举例
最小逃脱问题
解题思路
将m×n栅格→费用流网络
方法：
（1）将每个栅格点(i,j)拆成v（i,j,1)和v(i,j,2)
（2）（i,j)的4个邻点变为8个顶点
(i,j)是起始点
cap=1
cost=0
V(I,j,1)
V(I,j,2)
V(i-1,j,1)
V(i+1,j,1)
V(i,j-1,1)
V(i,j+1,1)
1
1
1
1
1
1
1
1
网络流算法应用举例
最小逃脱问题
解题思路
将m×n栅格→费用流网络
方法：
（1）将每个栅格点(i,j)拆成v（i,j,1)和v(i,j,2)
（2）（i,j)的4个邻点变为8个顶点
(i,j)是边界点
cap=1
cost=0
V(I,j,1)
V(I,j,2)
V(i-1,j,2)
V(i+1,j,2)
V(i,j-1,2)
V(i,j+1,2)
1
1
1
1
1
1
1
1
网络流算法应用举例
最小逃脱问题
解题思路
将m×n栅格→费用流网络
方法：
（1）将每个栅格点(i,j)拆成v（i,j,1)和v(i,j,2)
（2）（i,j)的4个邻点变为8个顶点
（3）增加源S，从S到所有起始点的边（s, v(I,j,1))
cap=1
cost=0
V(i,j,1)
V(I,j,2)
V(i-1,j,1)
V(i+1,j,1)
V(i,j-1,1)
V(i,j+1,1)
1
0
1
1
1
1
1
1
1
1
V(i1,j1,1)
V(i2,j2,1)
1
0
1
0
s
网络流算法应用举例
最小逃脱问题
解题思路
将m×n栅格→费用流网络G
方法：
（1）将每个栅格点(i,j)拆成v（i,j,1)和v(i,j,2)
（2）（i,j)的4个邻点变为8个顶点
（3）增加源S，从S到所有起始点的边（s, v(I,j,1))
（4）增加汇t，所有边界点到t的边（v(i,j,2), t)
cap=1
cost=0
V(i,j,1)
V(I,j,2)
V(1,j,1)
V(m,j,1)
V(i,j-1,1)
V(i,j+1,1)
1
0
1
1
1
1
1
1
1
1
V(i1,j1,1)
V(i2,j2,1)
1
0
1
0
s
V(1,j,2)
V(m,j,2)
V(i,j-1,2)
V(i,j+1,2)
t
1
0
1
0
网络流算法应用举例
最小逃脱问题
解题思路
将m×n栅格→费用流网络G
求G的最小费用最大流f. |f|=ff时，最大流f对应一最小逃脱。
求G的最大流f.|f|=ff时，f对应一逃脱，但不一定最小。
网络流算法应用举例
最佳航空路线问题
问题描述
已知：航空图（顶点为城市，边为直达航线）
求：途径城市最多的旅行路线
条件：（1）起点（西端点）东端点起点
（2）每个城市只经过1次。
V
Y
E
C
W
T
M
H
网络流算法应用举例
最佳航空路线问题
解题思路
采用最小费用流算法
原问题→费用流网络G
方法：(1)将每个城市i拆成2个顶点，增加连接两个顶点的有向边，容量为1（该市只能访问1次），cost=0.(使该市尽可能被访问）
V
Y
E
C
W
T
M
H
V ’
Y’
E’
C’
W’
T ’
M’
H’
1，0
网络流算法应用举例
最佳航空路线问题
解题思路
采用最小费用流算法
原问题→费用流网络G
方法：（2）若i到j有航线（i<j),增加边(i’,j).
容量为1（航线只能过1次），
单位流量费用=j-i+1 (中间间隔的城市数）
V
Y
E
C
W
T
M
H
V ’
Y’
E’
C’
W’
T ’
M’
H’
1，0
1，5
网络流算法应用举例
最佳航空路线问题
解题思路
采用最小费用流算法
原问题→费用流网络G
方法：（3）顶点v与v’之间边容量为2（起点可经过2次）
顶点H与H’之间边容量为2（东端点经过2次）
V
Y
E
C
W
T
M
H
V ’
Y’
E’
C’
W’
T ’
M’
H’
2，0
1，5
1，0
1，0
1，0
1，0
1，0
1，0
2，0
1
2
3
4
5
6
网络流算法应用举例
最佳航空路线问题
解题思路
采用最小费用流算法
原问题→费用流网络G
方法：（4）顶点V为源
顶点H’为汇
S
Y
E
C
W
T
M
H
V ’
Y’
E’
C’
W’
T ’
M’
t
2，0
1，5
1，0
1，0
1，0
1，0
1，0
1，0
2，0
1
2
3
4
5
6
网络流算法应用举例
最佳航空路线问题
解题思路
采用最小费用流算法
原问题→费用流网络G
求G最小费用最大流，得到两条流（1至n和n到1）
S
Y
E
C
W
T
M
H
V ’
Y’
E’
C’
W’
T ’
M’
t
2，0
1，5
1，0
1，0
1，0
1，0
1，0
1，0
2，0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
最大获益
CS&T公司在前期市场调查和站址勘测之后，公司得到了一共 N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的：建立第 i个通讯中转站需要的成本为 Pi（1≤i≤N）。
所有期望中的用户群，一共 M个。关于第 i个用户群的信息概括为 Ai, Bi和 Ci：这些用户会使用中转站 Ai和中转站 Bi进行通讯，公司可以获益 Ci。（1≤i≤M, 1≤Ai, Bi≤N） CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）
输入数据
5 5 中转站个数，客户群数
1 2 3 4 5 中转站建设成本
1 2 3 客户群1使用的中转站及收益
2 3 4
1 3 3
1 4 2
4 5 3
思路：
选择客户群的集合Y，需建立的中转站的集合X。净收益为A中客户群的收益减去B中所建中转站的费用和。
建立二分图G=（X，Y），X节点为所有中转站，每个中转站i用Xi表示，连接容量为Pi的弧s→Xi。
Y节点为所有客户群，每个客户群i用Yi表示，连接一条容量为Ci的弧Yi→ t。
如果客户i要用到中转站j,则连接一条容量
为无穷大的弧Xj →Yi。
该网络的最大流可求。
网络最大流的意义：
根据最大流最小割定理，可得到网络容量最小的割集C。
去掉割集C中的所有弧以后，s,t就分属两个不同的连通分支V1和V2，s,t不再连通。
V2中包含的客户群j就是被选择的客户群。V2种包含的中转站i被建立。
这样割集中包含S到V2中被建立的中转站建的弧（权Pi为建立成本）及V1中客户群j（未被选中的）到t的弧（权为其收益Cj，而被选中客户群k的收益Ck未被计算在切割中。
网络最大流的意义：
割容量（即最大流）为：
Sum{P（i）}+Sum{C(j)}
i-属于V2的中转站，被选中
j-属于V1的客户群，未被选中
则总收益=C-[Sum{P（i）}+Sum{C(j)}]
=C-最大流流量
网络最大流的意义：
根据最大流最小割定理，可得到网络容量最小的割集C。
去掉割集C中的所有弧以后，s,t就分属两个不同的连通分支V1和V2，s,t不再连通。
V2中包含的客户群j就是被选择的客户群。V2种包含的中转站i被建立。
这样割集中包含S到V2中被建立的中转站建的弧（权Pi为建立成本）及V1中客户群j（未被选中的）到t的弧（权为其收益Cj，而被选中客户群k的收益Ck未被计算在切割中。
End!
* flow: abstract entity generated at source, transmitted across edges, absorbed at sink
* flow conservation is analogous to Kirchoff's law
* flow: abstract entity generated at source, transmitted across edges, absorbed at sink
* flow conservation is analogous to Kirchoff's law
