基础
流网络性质
容量限制：对所有的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)。
残流网络
在给定的流网络G=(V,E)中，设f为G中的一个流，并考察一对顶点u，v∈V，在不超过容量c(u,v)的条件下，从u到v之间可以压入的额外网络流量，就是(u,v)的残留容量。残留容量的定义为：cf(u,v)=c(u,v)-f(u,v)。【f指已有的流量】而由所有属于G的边的残留容量所构成的带权有向图就是G的残留网络。
性质：残流网络中的流与原流相加一定也是原流网络的一个可行流。很明显嘛…若f是G中的一个流，Gf是由G导出的残留网络，f’是Gf中的一个流，则f+f’是G中一个流，且其值|f+f’|=|f|+|f’|。
增广路径
增广路径p为残流网络Gf中从s到t的一条简单路径。根据残留网络的定义，在不违反容量限制的条件下，G中所对应的增广路径上的每条边(u,v)可以容纳从u到v的某额外正网络流。而能够在这条路径上的网络流的最大值一定是p中边的残留容量的最小值。
最大量为p的残留网络定义为：cf(p)=min{cf(u,v) | (u,v)在p上}【残流网络cf中剩余容量最小的容量即为残流网络的最大量p】
割
流网络G(V,E)的割(S,T)将V划分成为S和T=V-S两部分，使得s∈S，t∈T。【顶点被割分成两部分】
如果f是一个流，则穿过割(S,T)的净流被定义为f(S,T)=∑f(x,y) (x∈S,y∈T)【净流：割分为的两部分顶点之间的流量和】
割(S,T)的容量为c(S,T)。【和净流定义类似，为S->V中所有顶点对(u,v)的容量和】
一个网络的最小割就是网络中所有割中具有最小容量的割。
设f为G中的一个流，且(S,T)是G中的一个割，则通过割(S,T)的净流f(S,T)=|f|。
证明：f(X,Y)=∑f(u,v)，其中u∈X，v∈Y
所以得到结论：最小割对应的流就是该流网络最大流
最大流最小割定理
如果f是具有源s和汇点t的流网络G=(V,E)中的一个流，则下列条件是等价的：
1) f是G中一个最大流。
2) 残留网络Gf不包含增广路径。
3) 对G的某个割(S,T)，有|f|=c(S,T)。
增广路算法（Edmonds-Karp算法）
struct Edge{
int from,to,cap,flow;
Edge(
int u,
int v,
int c,
int f):from(u),to(v),cap(c),flow(f){}
};
struct EK{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
int a[maxn];
int p[maxn];
void init(
int n){
for(
int i=
0;i<n;i++) G[i].clear;
edges.clear();
}
void addEdge(
int from,
int to,
int cap){
edges.push_back(Edge(from,to,cap,
0));
edges.push_back(Edge(to,from,cap,
0));
m=edges.size();
G[from].push_back(m-
2);
G[to].push_back(m-
1);
}
int maxFlow(
int s,
int t){
int flow=
0;
while(
true){
memset(a,
0,
sizeof(a));
queue<int> Q;
Q.push(s);
a[s]=INF;
while(!Q.empty()){
int cur=Q.front(); Q.pop();
for(
int i=
0;i<G[cur].size();i++){
Edge &e=edges[G[cur][i]];
if(!a[e.to] && e.cap>e.flow){
p[e.to]=G[cur][i];
a[e.to]=min(a[cur],e.cap-e.flow);
Q.push(e.to);
}
}
if(a[t])
break;
}
if(!a[t])
break;
for(
int u=t;u!=s;u=edges[p[u]].from){
edges[p[u]].flow+=a[t];
edges[p[u]^l].flow-=a[t];
}
flow+=a[t];
}
return flow;
}
};
转载于:https://www.cnblogs.com/leotan0321/p/6081370.html
