图中哪个网络没有可行流

① 怎么样求网络的最大流和最小截集

首先是网络流中的一些定义：
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));
}
}

② 帮我解释下网络流

必须知识：最短路径问题
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问题。(*)

③ 网络理论的最大流量问题

当物质流或信息流通过给定的网络时（图1）,在流过每条边的流量xij不超过该边允许通过的流量cij的条件下,求出从发点s向收点t输出的最大流量f，即在满足的条件下,使f最大。最大流量问题是一个特殊的线性规划问题，有许多求解方法。一种有效的计算方法是福特-富尔克森法，它是根据最大流量-最小割集原理，通过标号算法，求出在上述约束条件下从发点s到收点t的最大流量f 的数值。其计算步骤如下：①绘制一个能满足上述约束条件的网络可行流（图2）。边上的数字为允许流量cij，括号内的数字为给定的可行流。②找出一条增广链。增广链是指从发点s到收点t的链中，满足正向边上xij<cij和反向边上xji>0的链。图2中用粗线表示的{vs，v2,v3,v4,v6,vt} 是一条增广链。其中【v2,v3】为反向边,其余均为正向边。③调整可行流,即在增广链的各边上,属正向边加上一个修正量ε,属反向边减去一个修正量ε,即xij+εj，xji-εj。εj值由下式决定:当xij<cij时

④ 运筹学中的网络最大流问题，该怎样确定初始可行流急，在线等

一般为选取零流为初始的可行流！

⑤ 运筹学网络最大流问题中逆向流也可以是可行流吗

楼上的回答驴唇不对马嘴。

你说的可行流是什么概念？是一种流量方案吗？网络流是有向图，逆向流不能算可行流。不过如果你说的可行流是寻找最大流时的增广路，可以走逆向流，这样可以将流量倒退回去。有问题请补充。

⑥ 高分：网络流问题

一、引言

网络流算法是一种高效实用的算法，相对于其它图论算法来说，它的模型更加复杂，编程复杂度也更高。但是它综合了图论中的其它一些算法（如最短路径、宽度搜索算法），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的非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，且矿石比较多情况下，两种模型的网络流算法都无法求解。在实际的应用中问题经常都只要求近似解，此时还可用综合一些其它算法来求解。

四、结束语

综上所述，网络流算法中模型的优化是网络流算法提高效率的根本。我们要根据实际问题，从减少顶点及边的角度综合考虑如何对模型进行优化，选择适当的模型，以提高算法的效率。对于有些题目，解题的各种模型各有优劣时，还可通过程序自动分析测试数据，以决定何种情况下采用何种模型，充分发挥各种模型的优点，以达到优化程序效率的目的。

⑦ 网络流的资料

编辑本段定义
图论中的一种理论与方法，研究网络上的一类最优化问题 。1955年 ，T.E. 哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D＝ （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问 ：若从起点v1将物资运送到终点v6去 ，应选择那条路线才能使总运输距离最短�这样一类问题称为最短路问题 。 如果把上图看作一个输油管道网 ， v1 表示发送点，v6表示接收点，其他点表示中转站 ，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。
最大流理论是由福特和富尔克森于 1956 年创立的 ，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善 。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。
目前网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

网络流算法
一、网络流的基本概念
先来看一个实例。
现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下图：
每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？
这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。
若有向图G=(V,E)满足下列条件：
1、 有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。
2、 有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。
3、 每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。
则称之为网络流图，记为G = (V, E, C)
譬如图5-1就是一个网络流图。
1．可行流
对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。
1、 每一条弧(i,j)有fij≤cij。
2、 除源点S和汇点T以外的所有的点vi，恒有：
该等式说明中间点vi的流量守恒，输入与输出量相等。
3、 对于源点S和汇点T有：
这里V(f)表示该可行流f的流量。
例如对图5-1而言，它的一个可行流如下：
流量V(f) = 5。
2．可改进路
给定一个可行流f=。若fij = cij，称<vi, vj>为饱和弧；否则称<vi, vj>为非饱和弧。若fij = 0，称<vi, vj>为零流弧；否则称<vi, vj>为非零流弧。
定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。
譬如在图5-1中，P = (S, V1, V2, V3, V4, T)，那么
P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>}
P- = {<V4, V3>}
给定一个可行流f，P是从S到T的一条道路，如果满足：
那么就称P是f的一条可改进路。（有些书上又称：可增广轨）之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。具体方法下一节会重点介绍，此不赘述。
3．割切
要解决网络最大流问题，必须先学习割切的概念和有关知识。
G = (V, E, C)是已知的网络流图，设U是V的一个子集，W = V\U，满足S U，T W。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。
对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：
例如图5-1中，令U = {S, V1}，则W = {V2, V3, V4, T}，那么
C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4>=8+4+4+1=17
定理：对于已知的网络流图，设任意一可行流为f，任意一割切为(U, W)，必有：V(f) ≤ C(U, W)。
通俗简明的讲：“最大流小于等于最小割”。这是“流理论”里最基础最重要的定理。整个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。
下面我们给出证明。
网络流、可改进路、割切都是基础的概念，应该扎实掌握。它们三者之间乍一看似乎风马牛不相干，其实内在联系是十分紧密的。
二、求最大流
何谓最大流？首先它必须是一个可行流；其次，它的流量必须达到最大。这样的流就称为最大流。譬如对图5-1而言，它的最大流如下：
下面探讨如何求得最大流。
在定义“可改进路”概念时，提到可以通过一定规则修改“可改进路”上弧的流量，可以使得总流量放大。下面我们就具体看一看是什么“规则”。
对可改进路P上的弧<vi, vj>，分为两种情况讨论：
第一种情况：<vi, vj>∈P+，可以令fij增加一个常数delta。必须满足fij + delta ≤ cij，即delta ≤ cij – fij。
第二种情况：<vi, vj>∈P-，可以令fij减少一个常数delta。必须满足fij - delta ≥ 0，即delta ≤ fij
根据以上分析可以得出delta的计算公式：
因为P+的每条弧都是非饱和弧，P-的每条弧都是非零流弧，所以delta > 0。
容易证明，按照如此规则修正流量，既可以使所有中间点都满足“流量守恒”（即输入量等于输出量），又可以使得总的流量有所增加（因为delta > 0）。
因此我们对于任意的可行流f，只要在f中能找到可改进路，那么必然可以将f改造成为流量更大的一个可行流。我们要求的是最大流，现在的问题是：倘若在f中找不到可改进路，是不是f就一定是最大流呢？
答案是肯定的。下面我们给出证明。
定理1 可行流f是最大流的充分必要条件是：f中不存在可改进路。
证明：
首先证明必要性：已知最大流f，求证f中不存在可改进路。
若最大流f中存在可改进路P，那么可以根据一定规则（详见上文）修改P中弧的流量。可以将f的流量放大，这与f是最大流矛盾。故必要性得证。
再证明充分性：已知流f，并且f中不存在可改进路，求证f是最大流。
我们定义顶点集合U, W如下：
（a） S∈U，
（b） 若x∈U，且fxy<cxy，则y∈U;
若x∈U，且fyx>0，则y∈U。
（这实际上就是可改进路的构造规则）
（c） W = V \ U。
由于f中不存在可改进路，所以T∈W；又S∈U，所以U、W是一个割切（U, W）。
按照U的定义，若x∈U，y∈W，则fxy = cxy。若x∈W，y∈U，则fxy = 0。
所以，
又因 v(f)≤C(U,W)
所以f是最大流。得证。
根据充分性证明中的有关结论，我们可以得到另外一条重要定理：
最大流最小割定理：最大流等于最小割，即max V(f) = min C(U, W)。
至此，我们可以轻松设计出求最大流的算法：
step 1. 令所有弧的流量为0，从而构造一个流量为0的可行流f（称作零流）。
step 2. 若f中找不到可改进路则转step 5；否则找到任意一条可改进路P。
step 3. 根据P求delta。
step 4. 以delta为改进量，更新可行流f。转step 2。
step 5. 算法结束。此时的f即为最大流。
三、最小费用最大流
1．问题的模型
流最重要的应用是尽可能多的分流物资，这也就是我们已经研究过的最大流问题。然而实际生活中，最大配置方案肯定不止一种，一旦有了选择的余地，费用的因素就自然参与到决策中来。
图5-8是一个最简单的例子：弧上标的两个数字第一个是容量，第二个是费用。这里的费用是单位流量的花费，譬如fs1=4，所需花费为3*4=12。
容易看出，此图的最大流（流量是8）为：fs1 = f1t = 5, fs2 = f2t = 3。所以它的费用是：3*5+4*5+7*3+2*3 = 62。
一般的，设有带费用的网络流图G = (V, E, C, W)，每条弧<Vi, Vj>对应两个非负整数Cij、Wij，表示该弧的容量和费用。若流f满足：
(a) 流量V(f)最大。
(b) 满足a的前提下，流的费用Cost(f) = 最小。
就称f是网络流图G的最小费用最大流。
2．算法设计
我们模仿求最大流的算法，找可改进路来求最小费用最大流。
设P是流f的可改进路，定义 为P的费用（为什么如此定义？）。如果P是关于f的可改进路中费用最小的，就称P是f的最小费用可改进路。
求最小费用最大流的基本思想是贪心法。即：对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。这样的得到的最大流必然是费用最小的。
算法可描述为：
step 1. 令f为零流。
step 2. 若无可改进路，转step 5；否则找到最小费用可改进路，设为P。
step 3. 根据P求delta（改进量）。
step 4. 放大f。转step 2。
step 5. 算法结束。此时的f即最小费用最大流。
至于算法的正确性，可以从理论上证明。读者可自己思考或查阅有关运筹学资料。
2．最小费用可改进路的求解
求“最小费用可改进路”是求最小费用最大流算法的关键之所在，下面我们探讨求解的方法。
设带费用的网络流图G = (V, E, C, W)，它的一个可行流是f。我们构造带权有向图B = (V’, E’)，其中：
1、 V’ = V。
2、 若<Vi, Vj>∈E，fij<Cij，那么<Vi, Vj>∈E’，权为Wij。
若<Vi, Vj>∈E，fij>0，那么<Vj, Vi>∈E’，权为-Wij。
显然，B中从S到T的每一条道路都对应关于f的一条可改进路；反之，关于f的每条可改进路也能对应B中从S到T的一条路径。即两者存在一一映射的逻辑关系。
故若B中不存在从S到T的路径，则f必然没有可改进路；不然，B中从S到T的最短路径即为f的最小费用可改进路。
现在的问题变成：给定带权有向图B = (V’, E’)，求从S到T的一条最短路径。
考虑到图中存在权值为负数的弧，不能采用Dijkstra算法；Floyd算法的效率又不尽如人意——所以，这里采用一种折衷的算法：迭代法。
设Short[k]表示从S到k顶点的最短路径长度；从S到顶点k的最短路径中，顶点k的前趋记为Last[k]。那么迭代算法描述如下：（为了便于描述，令n = |V’|，S的编号为0，T的编号为n+1）
step 1. 令Short[k]  +∞（1≤k≤n+1），Short[0]  0。
step 2. 遍历每一条弧<Vk, Vj>。若Short[k] + <k, j> < Short[j]，则令Short[j]  Short[k] + <k, j>，同时Last[j]  k。倘不存在任何一条弧满足此条件则转step 4。
step 3. 转step 2.
step 4. 算法结束。若Short[n + 1]= +∞，则不存在从S到T的路径；否则可以根据Last记录的有关信息得到最短路径。
一次迭代算法的时间复杂度为O(kn2)，其中k是一个不大于n的变量。在费用流的求解过程中，k大部分情况下都远小于n。
3．思维发散与探索
1）可改进路费用：“递增！递增？”
设f从零流到最大流共被改进了k次，每i次选择的可改进路的费用为pi，那么会不会有p1≤p2≤p3≤……≤pk呢？
2）迭代法：“小心死循环！嘿嘿……”
迭代法会出现死循环吗？也就是说，构造的带权有向图B中会存在负回路吗？
3）费用：“你在乎我是负数吗？”
网络流图中的费用可以小于零吗？
4）容量：“我管的可不仅是弧。”
网络流图中的“容量”都是对弧而言的，但若是给每个顶点也加上一个容量限制：即通过此顶点的流量的上限；任务仍然是求从S到T的最小费用最大流。你能解决吗？
四、有上下界的最大流
上面讨论的网络流都只对每条弧都限定了上界（其实其下界可以看成0），现在给每条弧<Vi, Vj>加上一个下界限制Aij（即必须满足Aij≤fij）。
例如图5-9：
弧上数字对第一个是上界，第二个是下界。若是撇开下界不看，此图的最大流如图5-10(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了，具体方案见图5-10(b)。
那么有上下界的网络最大流怎么求呢？
一种自然的想法是去掉下界，将其转化为只含上界的网络流图。这种美好的愿望是可以实现的。具体方法如下：
设原网络流图为G = (V, E, C, A)，构造不含下界的网络流图G’ = (V’, E’, C’)：
1、 V’ = V∪{S’, T’}
2、 对每个顶点x，令 ，若h-(x)≠0，就添加一条弧<S’, x>，其上界为h-(x)。
3、 对每个顶点x，令 ，若h+(x)≠0，就添加一条弧<x, T’>，其上界为h+(x)。
4、 对于任何<Vi, Vj>∈E，都有<Vi, Vj>∈E’，其上界C’ij = Cij – Aij。
5、 新增<T, S>∈E’，其上界CTS = +∞。
在G’中以S’为源点、T’为汇点求得最大流f’。若f’中从S’发出的任意一条弧是非饱和弧，则原网络流图没有可行流。否则可得原图的一个可行流f = f’ + A，即所有的fij = f’ij + Aij。（其正确性很容易证明，留给读者完成）
然后再求可改进路（反向弧<Vi, Vj>必须满足fij≥Aij，而非fij≥0），不断放大f，直到求出最大流。
我们看到，上几节所讨论的一种可行网络流实际上是{Aij = 0}的一种特殊网络流，这里提出的模型更一般化了。解决一般化的复杂问题，我们采取的思路是将其转化为特殊的简单问题，加以研究、推广，进而解决。这是一种重要的基本思想：化归——简单有效。基于这种思想，请读者自行思考解决：
1、 有上下界的最小流。
2、 有上下界的最小费用最大流。
五、多源点、多汇点的最大流
已知网络流图有n个源点S1、S2、……、Sn，m个汇点T1、T2、……、Tm，，求该图的最大流。这样的问题称为多源点、多汇点最大流。
它的解决很简单：
1、 增设一个“超级源”S’，对每个源点Si，新增弧<S’, Si>，容量为无穷大。
2、 增设一个“超级汇”T’，对每个汇点Ti，新增弧<Ti, T’>，容量为无穷大。
3、 以S’为源点、T’为汇点求最大流f。
4、 将f中的S’和T’去掉，即为原图的最大流。
算法正确性显然。
六、顶点有容量限制的最大流
上一节已经提出了这个问题，即对于进出每个顶点的流量也规定一个上限，这样的最大流如何求？
既然我们已经解决了“边限制”问题，现在何不把“点限制”问题转化为“边限制”呢？具体办法如下：
1、 对除源点和汇点之外的每个顶点i拆分成两个顶点i’和i’’。新增一条弧<i’, i’’>，其容量为点i的流量限制。
2、 对于原图中的弧<i, j>，我们将其变换成<i’’, j’>。
3、 对变换后的图求最大流即可。
这里我们又一次运用到了化归的思想：将未知的“点限制”问题转化为已知的“边限制”问题。
七、网络流与二部图的匹配
{二部图和匹配的定义可参见本书专门介绍二部图匹配的章节}
设二部图为G = (X, Y, E)。
增设点S’，对于所有i∈X，新增弧<S’, Xi>，容量为1；增设点T’，对于所有i∈Y，新增一条弧<Yi, T’>，容量也为1。原图中所有的弧予以保留，容量均为+∞。对新构造出来的网络流图以S’为源点、T’为汇点求最大流：流量即为最大匹配数；若弧<Xi, Yj>（i∈X，j∈Y）的流量非零，它就是一条匹配边。
二部图最大匹配问题解决。
那么二部图的最佳匹配问题又如何？
仍然按照上述方法构图。同时令原图中弧的费用保持不变；新增弧的费用置为0。然后以S’为源点、T’为汇点求最小费用最大流即可。最大流的费用即为原二部图最佳匹配的费用。

复制的我快吐了~