最大流（一）——各种思路
思考顺序：
先有容量限制c[] --> 有多种可能的网络流f[] --> 找最大流（流值|f|最大的流）
?
一、网络流
?
G=<V,E>为有向图
?
1. 容量为非负: 如果有向边(u,v) 存在，c(u,v)≥0； 如果有向边(u,v)不存在，c(u,v)=0
?
2. 网络流：
（1）容量限制：f(u,v)≤c(u,v)???????????????????????????????? ==> 单向流速受限
（2）反对称性：f(u,v)=-f(v,u)??????????????????????????????? ==> 在管道中向不同方向看，水流一面迎面而来，一面向前推我
（3）流守恒性：f(V-s-t,V)=0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ==> A. 中间顶点不存储流（流进=流出）
?????????????????????????????????????????????????????????????????????????????????? B. 进入中间顶点的正网络流=离开该点的正网络流
注意：
?????? 流守恒性也可以写作f(V,V-s-t)=0，即流入一个顶点的总流为0；
?????? 在f(V-s-t,V)或f(V,V-s-t)的中，其中每一元素可以为正可以为负，不要以为不能为负（这是“残留网络”中的限制，网络流不受限）
?
引理26.1: G=<V,E>是流网络，f是G的一个流。
?????????????? 定义f(X,Y)=∑f(x,y)，x∈X, y∈Y.
????????????? （1）任意X?V,???????????????????????? 则 f(X,X)=0??????????????????????? ==>反对称性:? f(u,v)= - f(v,u)
????????????? （2）任意X,Y?V, ? ?????????????????? 则f(X,Y)=-f(Y,X)????????????????? ==>（1）的推广
?
????????????? （3）X,Y,Z? V, X∩Y=????????????? 则f(X∪Y,Z)=f(X,Z)+f(Y,Z)
?
二、流值 和 最大流
?
1. 流f的值|f|=f(s,V)=f(V,t)： 源s送出多少水/汇t喝了多少水
2. 最大流问题： 给出流网络G（源点s，汇点t），希望从中找出流值|f*|最大的流f*， f*称为最大流
?
三、最大流问题求解
?
1. 三个理论基础 和 “最大流最小割定理”：
?
??? 理论一：“残留网络 residual network”
网络流图G ==决定唯一==> 有向边的残留容量 cf(u,v)=c(u,v)-f(u,v)
网络流图G ==决定唯一==> G导出的残留网络 Gf=<V,Ef>, Ef={(u,v)∈V×V: cf(u,v)>0}
??? （1）后者（残留网络）由满足条件的前者(残留容量严格＞0的有向边)组成
??? （2）残留网络中的所有有向边上的残留容量均>0. 如果认为残留容量cf(u,v)是残留网络的（有向）边的权值，则所有权值严格>0，∵不满足介个条件的有向边根本就通不过海选!
?
??? 理论二：“增广路径 augmenting path”
增广路径p: 残留网络Gf中从源点s到汇点t的一条简单路径。
增广路径p的残留容量： cf(p)=min{cf(u,v):? (u,v)在增广路径p上}
?
??? 理论三：“割 cut”
网络流G的割(S,T)，源点s∈S, 汇点t∈T。从S到T的边称为割边。
?
最大流最小割定理：
??? （1）f是G的一个最大流???????????????????????????????????? ==>达到流值|f|=f(s,V)最大
??? （2）残留网络Gf不包含增广路径???????????????????????? ==>不能再压入正网络流
??? （3）对G的某个割(S,T) ，存在|f|=c(S,T)???????? ?? ==>对最大流的限制来自最小容量的那个割
?
2. 求解最大流问题
?
??? 2.1 枚举算法
????????? 时间复杂度： O(2^|V|·|E|)
????????? 思路：枚举所有割(S,T)，找到容量c(S,T)最小的那个割的容量，即为最大流的流值
????????? 评价：算法复杂度高，因此仅当顶点个数|V|较少时适用（否则整数越界）；另外，它还不能给出得到最大流的具体的网络流，只是返回了最大流值。
??
?
参考资料：
另一个小盆友学习的心得：? http://hi.baidu.com/sheep_finalfreedom/blog/item/273772dc2cf5775994ee3795.html#0外国大牛的文章：http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited#1
?
?
弄到这里有点心力憔悴了，以后再继续看：
1. Dinic算法
2. 预流推进算法
