网络流看着很麻烦，实际搞清楚后就只剩建图了，主要是要先搞清定义（知晓定义的大佬请自行跳过）,然后搞定模板，最后练一下建图
有向边(在网络流中叫弧）
起点为u,终点为v且只能从u到v的边。
流量
弧上流过去的量f(u,v)（废话)
容量
弧的边权即为容量为c(u,v)
源点
入度为0的点s，s的流量一般为∞
汇点
出度为0的点t，流出t的流量为0（流进来的跑不了）
流
从一点流向另一点的流量，最大流即为流的最大的流量
网络
实际就是一张有向图，每条有向边（弧）的边权是容量，另外还有源点和汇点
残差网络
在残差网络中，每边的边权为c(u,v)-f(u,v)————实际就是把剩余的容量在另一张网络上体现出来
网络流的性质
容量限制 0<=f(u,v)<=c(u,v)
反对称性 f(v,u) = -f(u,v)——————这点很重要，相当于建了反边，用于调整网络流
流守恒性 流进u点的流量 = 流出u点的流量(s,t除外）
平衡条件
流入u点的流量=流出u点的流量
可行流
符合网络流性质的流
特殊的流
零流 f(u,v)=0;
伪流 只满足平衡条件，却不满足容量限制的流
弧的类型
饱和弧 f(u,v)=c(u,v)
非饱和弧 f(u,v)<c(u,v)
零流弧 f(u,v)=0
非零流弧 f(u,v)>0
历经千辛万苦，总算把网络流的定义说完了，下面开始网络流的算法。
Ford-Fulkerson方法
Ford-Fulkerson，简称FFA,更像是一种方法，而不是算法。（因为后文讲的EK实际上就是FFA用bfs实现）
此方法核心在于找增广路（就是从源点到汇点的可行流），然后进行调整即可，直到找不到增广路。
如图，在开始赏析这丑陋的图前，声明一下，（a,b）代表流量为a，容量为b。
第一次寻找增广路径，可能（因为FFA方法只要找增广路就行，找到哪条无所谓）会找到S->T的最大可行流量2，然后我们就要进行调整，就是流上的每条弧流量加上可行流量2（实际上程序中都是直接在残差网络中进行处理，原理一样，下文会讲）
然后继续寻找增广路，可能会找到S->1->T的最大可行流量2，然后按上次操作一样进行调整。
继续找，还能找到S->1->2->T的最大可行流量1，再进行调整
然后就发现找不到增广路了，可得知网络最大流为5。
总结一下，FFA其实就是
1.找增广路，找不到就结束。
2.进行调整。
但是，还没完。请观察如下一幅图。（这里是残差网络，实际上是作者偷懒）
于是发现找增广路时，可能找到S->2->1->T这条可行流，最大流量为1，然后找不到新的增广路，结束。
但显然我们能发现最大流量应为2，问题出在哪了呢？观察知找增广路时找的不是最优的，那该怎么办？于是采取建反向弧的思想（上文定义部分有提到），即建f(v,u)=-f(u,v),这样我们走错路后，可以寻找新的增广路进行调整（网络流非常大的一个优势就是可调整），最终找到最优的。
具体代码在这里就不写了，因为后文的EK实际上就是用BFS实现找增广路，我们在EK部分展示代码。（最主要的原因是DFS实现的太废了，时间复杂度太高，为O（mf）,f为最大流）
为什么DFS实现的FFA复杂度如此之高呢，再看张丑图
最大流应为200，但如果倒霉的话，就会S->1->2->T , S->2->1->T走上200趟。如果容量再大点，就……
问题：没找对路，浪费时间。
方法：找最短的路，可以用BFS实现。
于是，我们学会了Edmonds-Karp(EK)算法，实现详见代码。
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
bool v[100010];
struct node{
int from,to,ca,flow,fid,tid;
}e,match[100010];
vector<node> Map[100010];
int get_other(int x,node e){//寻找这条边的另一个点
if(x==e.from) return e.to;
else return e.from;
}
int get_left(int x,node e){//剩余容量
if(x==e.from) return e.ca-e.flow;
else return e.flow;
}
int add_flow(int x,node &e,int y){//调整流量
if(x==e.from) e.flow+=y;//正向边流量增加
else return e.flow-=y;//反向边流量减少
}
void add(int a,int b,int c){
e.from=a; e.to=b; e.ca=c; e.flow=0;//从a到b容量为c,流量为0
e.fid=Map[a].size(); e.tid=Map[b].size();
Map[a].push_back(e); Map[b].push_back(e);//链式前向星,这里建了反边
}
bool bfs(){
memset(v,0,sizeof(v));
memset(match,0,sizeof(match));
queue<int> q;
q.push(s); v[s]=1;
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=0;i<Map[x].size();i++){
node e=Map[x][i];
int b=get_other(x,e);
if(get_left(x,e)>0 && !v[b]){ //非饱和弧,即还有流量能流过去，并且要到的点没走过
v[b]=1;
match[b]=e; //到b的边设为e
q.push(b); //b入队
}
}
}
return v[t];//看有没有到t
}
int find(){
int i=t,mf=0x7ffffff;
while(i!=s){
mf=min(mf,get_left(get_other(i,match[i]),match[i]));
i=get_other(i,match[i]);
}//找最大可行流
i=t;
while(i!=s){
node e=match[i];
add_flow(get_other(i,e),Map[e.from][e.fid],mf);
add_flow(get_other(i,e),Map[e.to][e.tid],mf);
i=get_other(i,match[i]);
}//进行调整
return mf;
}
int main(){
cin>>n>>m;//n个点,m条边
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);//建边
}
cin>>s>>t; //读入源点和汇点
int ans=0;
while(bfs()) ans+=find();//bfs()寻找增广路,find调整
cout<<ans<<endl;
return 0;
}
EK的时间复杂度为O(nm^2),不过本蒻蒟不会证……
例题
草地排水 https://www.luogu.com.cn/problem/P2740
但是能否进行优化呢，可以看到，EK一次找1条增广路，并进行调整，未免有些浪费。那该如何一次找多条增广路呢？可以用DFS，那怎么在用DFS的同时，如何保证走最短的路呢？分层！
Dinic
进行分层后再用DFS寻找增广路并调整，就是此算法的基本思路。
分层：就是先用BFS确定每点的深度d(x)，然后搜索时延d(v)=d(u)+1的边去搜，就可以了。具体详见代码（实际上是P3376的代码）。
注意！！！本代码与EK不同的是本代码用的是残差网络！！！
#include<bits/stdc++.h>
using namespace std;
struct ee{
long long to,next,dis;
}e[100010];
long long head[100010],d[100010],cur[100010],cnt=-1,ans,n,m,s,t,inf=1e12;
void add(long long x,long long y,long long z){
e[++cnt].next=head[x];
e[cnt].to=y;
e[cnt].dis=z;
head[x]=cnt;
}//一个链式前向星，没什么好说的
bool bfs(){
memset(d,127,sizeof(d)); //初始化，每个点初始深度为极大值
d[s]=0; //源点深度为0
queue<int> q;
q.push(s);
for(int i=1;i<=n;i++) cur[i]=head[i]; //优化，每次将head存入cur,避免在dfs走重复的弧，详见dfs处
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=head[x];i!=-1;i=e[i].next){
if(d[e[i].to]>inf && e[i].dis>0){ //没去过且还有流量能流过去
d[e[i].to]=d[x]+1; //确定深度，分层
q.push(e[i].to);
if(e[i].to==t) return 1; //到终点，返回true,表示有从源点到汇点的可行流
}
}
}
return 0; //没找到汇点,返回false
}
long long dfs(int x,long long limit){ //x是当前节点，limit是流到x的流量
if(!limit || x==t) return limit; //当走到t，返回流量，以用来调整
long long flow=0,f; //flow是这点流出的流量,f是某条边流出的流量
for(int i=cur[x];i!=-1;i=e[i].next){ //这里不用head,而用cur,是为了避免走一条别走过的没价值的边走多次，浪费时间
cur[x]=i; //通过这种方式，是下回从i开始，而不是head[x]
int y=e[i].to;
if(e[i].dis>0 && d[y]==d[x]+1 && (f=dfs(y,min(limit,e[i].dis)))){ //有流量能流过去且d[y]=d[x]+1,是x的下一层，就继续搜索，limit与这条边的剩余容量取min
flow+=f; //从这点流出的流量
limit-=f; //这个点还剩的流量
e[i].dis-=f; //正向边剩余容量减去流出的，f(u,v)加f，那c(u,v)-f(u,v)就减f
e[i^1].dis+=f; //反向边剩余容量加上流出的，f(v,u)=-f(u,v),残差网络中可调整量加上f
if(!limit) break; //没流量了，退出
}
}
return flow; //返回流出的量
}
int main(){
memset(head,-1,sizeof(head));
long long x,y,z;
cin>>n>>m>>s>>t; //n个点,m条边
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
add(x,y,z); //正向边,z是剩余流量
add(y,x,0); //反向边,因为是残差网络,所以剩余流量为0
}
while(bfs()) ans+=dfs(s,inf); //不断bfs分层，然后dfs搜索
cout<<ans<<endl;
return 0;
}
这个是Dinic加上些基础优化的版本。
顺便说一句Dinic的时间复杂度为O(n^2m)(身为蒻蒟的我当然也不会证……）
至此，我们终于把网络流的定义和模板学完了！
至于建模，本蒻蒟向各位推荐题单
网络流从入门到入土 #1https://www.luogu.com.cn/training/12097，里面的题还是非常有利于建模的，这东西就跟dp一样，主要靠感觉以及少量小技巧。
本篇语言较为浅显，可能有所不明，欢迎在评论区留言提醒作者。
标签：最大,增广,int,flow,网络,long,流量,浅谈 From： https://www.cnblogs.com/cdx1221/p/16916043.html