假设 G(V,E) 是一个有限的有向图，它的每条边(u,v)∈E都有一个非负值实数的容量 c(u,v) 。如果(u,v)不属于E，我们假设 c(u,v) = 0 。我们区别两个顶点：一个源点 s 和一个汇点 t。一道网络流是一个对于所有结点 u 和 v 都有以下特性的实数函数f:V×V→R
容量限制 (Capacity Constraints):
f(u,v)≤c(u,v)一条边的流不能超过它的容量。
斜对称 (Skew Symmetry):
f(u,v)=-f(v,u)由 u 到 v 的净流必须是由 v 到 u 的净流的相反（参考例子）。（既然要看网络流，这是一定要知道的）
流守恒 (Flow Conservation):
除非 u = s 或 u = t ，否则Σ（w∈V）f(u,w)=0 一结点的净流是零，除了“制造”流的源点和“消耗”流的汇点。
注意 f(u,v) 是由 u 到 v 的净流。如果该图代表一个实质的网络，由 u 到 v 有 4 单位的实际流及由 _v_到 u 有 3 单位的实际流，那么 f(u,v) = 1 及 f(v,u) = − 1。
边的剩余容量 (Residual Capacity)是 cf(u,v) = c(u,v) − f(u,v)。这定义了以 Gf(V,Ef)表示的剩余网络 (Residual Network)，它显示可用的容量的多少。留意就算在原网络中由 u 到 v 没有边，在剩余网络乃可能有由 u 到 v 的边。因为相反方向的流抵消，减少由v到u的流等于增加由 u 到 v 的流。**扩张路径 (Augmenting Path)**是一条路径 (u1,u2...uk)，而 u1 =s、uk=t 及 cf(ui,ui+ 1) > 0，这表示沿这条路径传送更多流是可能的。
以上摘自百度百科
下面求最大流的两个算法基础思路都一样，就是求不断增广路。增广路是一条从s到t的路径，且上面的每一条边的剩余容量大于0。每求出一条增广路及其最小流量都要在这条路径上更新剩余流量，并将最小流量加到最大流中。
将每一条边的反向边也连起来，因为斜对称性，所以每次更新时，除了在边上减去增广路的最小流量，还要在反向边上加上最小流量。
至于为什么是对的。。。我还需要一段时间的沉淀来理解。。
Edmonds-Karp
直接在一张图上不断寻找增广路，然后不断更新。。
O(nm^2)
1e2 ~ 1e3
int head[N],ver[N*2],edge[N*2],Next[N*2],tot=1;
void add(int x,int y,int w){
ver[++tot]=y,edge[tot]=w;
Next[tot]=head[x],head[x]=tot;
}
int n,m,s,t,maxflow,v[N],incf[N],pre[N];
bool bfs(){
memset(v,0,sizeof(v));
queue<int> Q;
Q.push(s),v[s]=1;
incf[s]=inf;
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(!edge[i]||v[y])continue;
incf[y]=min(incf[x],edge[i]);
pre[y]=i,v[y]=1,Q.push(y);
if(y==t)return true;
}
}
return false;
}
void update(){
int x=t;
while(x!=s){
int i=pre[x];
edge[i]-=incf[t];
edge[i^1]+=incf[t];
x=ver[i^1];
}
maxflow+=incf[t];
}
void resetMaxflow(){
memset(head,0,sizeof(head));
tot=1,maxflow=0;
}
int main(){
ios::sync_with_stdio(false);
while(cin>>m>>n){
resetMaxflow();s=1,t=n;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z),add(y,x,0);
}
while(bfs())update();
cout<<maxflow<<endl;
}
}
Dinic
每次都遍历一整张图显然是可以继续优化的。
不断求出分层图，通过dfs求增广路并更新。
O(nm^2)
1e3 ~ 1e4
int head[N],ver[N*2],edge[N*2],Next[N*2],tot=1;
void add(int x,int y,int w){
ver[++tot]=y,edge[tot]=w;
Next[tot]=head[x],head[x]=tot;
}
int n,m,s,t,maxflow,d[N];
bool bfs(){
queue<int> Q;
memset(d,0,sizeof(d));
Q.push(s),d[s]=1;
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(!edge[i]||d[y])continue;
Q.push(y),d[y]=d[x]+1;
if(y==t)return true;
}
}
return false;
}
int dinic(int x,int flow){
if(x==t)return flow;
int rest=flow,k;
for(int i=head[x];i&&rest;i=Next[i]){
int y=ver[i];
if(!edge[i]||d[y]!=d[x]+1)continue;
k=dinic(y,min(rest,edge[i]));
if(!k)d[y]=0;
edge[i]-=k,edge[i^1]+=k;
rest-=k;
}
return flow-rest;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z),add(y,x,0);
}
int flow=0;
while(bfs())
while(flow=dinic(s,inf))
maxflow+=flow;
cout<<maxflow<<endl;
}