最大流
概念（一般形式、一般模型）：
在一张有向图中，给定源点、汇点，每条边单位时间可以流x容量的水。有无限的水从源点流入，从汇点流出。求单位时间内，从汇点流出的水的最大值。
（网络流）最大流-增广路算法
核心思路：
每次找到一条可以流水的路径，将其称为增广路。增广路的所以算法本质上都是找出增广路，将增广路注入水，然后继续寻找增广路，直到没有增广路可寻。
EK（Edmond—Karp）算法
基本思路：
每次使用bfs寻找出一条最短增广路（木桶效应，假如没有最短增广路，那么绝对不会有其他增广路），对其进行注水操作，即找出这条路径中最小容量的边，将这条路径所有的边的容量都减去这条边的容量，重复此操作，直至没有增广路可寻。
细节：
1.在建立边时，应建立一条权值为0的反边。
原因：假如第一次进行注水操作时没有选择最优路径，这条边可以让我们有更正的余地。
2.根据 细节1 ，每条边进行- or + 一个值的操作时，其反边应该相应的进行 - or + 这个值的相反数的操作
代码（洛谷 P3376 【模板】网络最大流）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long min(long long a,long long b){
return a<b?a:b;
}
struct rec{
int e,nex;
long long d;
}z[1000010];
int n,m,s,t;
int en=1,fi[210000];
long long max_flow,min_flow;
void add(int s,int e,long long d){
z[++en].e=e;
z[en].nex=fi[s];
fi[s]=en;
z[en].d=d;
}
int cnt[210];
struct que{
int l,r;
int a[4000010];
void memsets(){
l=1,r=0;
}
void pop(){
l++;
}
void push(int x){
a[++r]=x;
}
int front(){
return a[l];
}
int size(){
return r-l+1;
}
bool empty(){
return r-l+1<=0;
}
}q;
struct pr{
int e,i;
}pre[210];
bool bfs(){
memset(pre,0,sizeof(pre));
min_flow=1e18;
memset(cnt,0,sizeof(cnt));
q.memsets();
q.push(s);
int x;
cnt[s]=true;
while (q.empty()==false){
x=q.front();
q.pop();
for (int i=fi[x];i!=0;i=z[i].nex){
if (z[i].d==0) continue;
if (cnt[z[i].e]==true) continue;
pre[z[i].e].e=x;
pre[z[i].e].i=i;
if (z[i].e==t) return true;
q.push(z[i].e);
cnt[z[i].e]=true;
}
}
return false;
}
void dfs(){
for (int i=t;i!=s;i=pre[i].e){
min_flow=min(min_flow,z[pre[i].i].d);
}
max_flow+=min_flow;
for (int i=t;i!=s;i=pre[i].e){
z[pre[i].i].d-=min_flow;
z[pre[i].i^1].d+=min_flow;
}
return ;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=m;i++){
int ss,e;
long long d;
scanf("%d%d%lld",&ss,&e,&d);
add(ss,e,d);add(e,ss,0);
}
while (bfs()==true){
dfs();
}
printf("%lld",max_flow);
return 0;
/*
5 5 1 5
1 2 4
2 3 3
2 4 3
3 5 100
4 5 100
*/
}
Dinic
基本思路：
EK算法 每次只找出一条增广路，时间复杂度过高，由此诞生了 Dinic算法。
Dinic算法 每次进行bfs的时候，将寻找增广路的操作改为了建立分层图，从源点->汇点将每个点都赋值一个高度值d[i]。赋值操作如下：
当前队列头部元素：front，当前边值不为0（假如当前边值为0，则没有增广的必要）时，假如此边另一方点e的d[e]仍然为初始值，则赋值：q[e]=q[front]+1。
同时寻找增广路的操作也变为了dfs。在dfs中，flow代表当前增广路中的最小值,used代表当前已经流了多少容量的水，假如当前边容量不为0且q[z[i].e]==q[x]+1则将此增广路延续到下一个点，直到搜索到汇点。假如当前搜索不到汇点，则说明没有增广路可寻，退出 Dinic算法。
易错点：注意要判定当前边权值是否为0
代码（题目同上）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long min(long long a,long long b){
return a<b?a:b;
}
struct rec{
int e,nex;
long long d;
}z[1000010];
int n,m,s,t;
int en=1,fi[210000];
long long max_flow,min_flow;
void add(int s,int e,long long d){
z[++en].e=e;
z[en].nex=fi[s];
fi[s]=en;
z[en].d=d;
}
int cnt[210];
struct que{
int l,r;
int a[4000010];
void memsets(){
l=1,r=0;
}
void pop(){
l++;
}
void push(int x){
a[++r]=x;
}
int front(){
return a[l];
}
int size(){
return r-l+1;
}
bool empty(){
return r-l+1<=0;
}
}q;
struct pr{
int e,i;
}pre[210];
bool bfs(){
memset(pre,0,sizeof(pre));
min_flow=1e18;
memset(cnt,0,sizeof(cnt));
q.memsets();
q.push(s);
int x;
cnt[s]=true;
while (q.empty()==false){
x=q.front();
q.pop();
for (int i=fi[x];i!=0;i=z[i].nex){
if (z[i].d==0) continue;
if (cnt[z[i].e]==true) continue;
pre[z[i].e].e=x;
pre[z[i].e].i=i;
if (z[i].e==t) return true;
q.push(z[i].e);
cnt[z[i].e]=true;
}
}
return false;
}
void dfs(){
for (int i=t;i!=s;i=pre[i].e){
min_flow=min(min_flow,z[pre[i].i].d);
}
max_flow+=min_flow;
for (int i=t;i!=s;i=pre[i].e){
z[pre[i].i].d-=min_flow;
z[pre[i].i^1].d+=min_flow;
}
return ;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=m;i++){
int ss,e;
long long d;
scanf("%d%d%lld",&ss,&e,&d);
add(ss,e,d);add(e,ss,0);
}
while (bfs()==true){
dfs();
}
printf("%lld",max_flow);
return 0;
/*
5 5 1 5
1 2 4
2 3 3
2 4 3
3 5 100
4 5 100
*/
}
ISAP(Improved Shortest Augumenting Path）
基本思路：
Dinic算法 还是太慢了，没事干的科学家们有搞出来了 ISAP算法 :P 假如 bfs只进行一次，还能求最大流吗？答案是肯定的，这就是ISAP！！！
ISAP算法 与 Dinic算法 有相似之处，同样需要bfs构造分层图，dfs进行统计。但是分层图是从汇点往源点开始建立，每次dfs时假如当前节点还可以往后流水，则将其高度加1。假如分层图出现断层，或者说源点的高度达到了n，则退出算法。
代码（题目同上）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct rec{
int e,nex;
long long d;
}z[250000];
int en=1,cur[1010],fi[1010];
void add(int s,int e,long long d){
z[++en].e=e;
z[en].d=d;
z[en].nex=fi[s];
fi[s]=en;
}
struct que{
int l,r;
int a[40010];
void memsets(){
l=1;r=0;
}
void pop(){
++l;
}
void push(int x){
a[++r]=x;
}
int front(){
return a[l];
}
bool empty(){
return r-l+1==0;
}
int size(){
return r-l+1;
}
}q;
int n,m,s,t;
int d[1010],cnt[1010];
void bfs(){
memset(d,-1,sizeof(d));
memset(cnt,0,sizeof(cnt));
d[t]=0;
cnt[0]++;
q.push(t);
while (q.empty()==false){
int x=q.front();
q.pop();
for (int i=fi[x];i!=0;i=z[i].nex){
if (d[z[i].e]==-1){
d[z[i].e]=d[x]+1;
q.push(z[i].e);
cnt[d[z[i].e]]++;
}
}
}
}
long long max_flow;
long long dfs(int x,long long flow){
if (x==t) return flow;
long long used=0;
for (int i=cur[x];i!=0;i=z[i].nex){
cur[x]=i;
if (z[i].d==0||d[z[i].e]+1!=d[x]) continue;
long long w=dfs(z[i].e,min(flow-used,z[i].d));
z[i].d-=w;
z[i^1].d+=w;
used+=w;
if (used==flow) return used;
}
cnt[d[x]]--;
if (cnt[d[x]]==0) d[s]=n+1;
d[x]++;
cnt[d[x]]++;
return used;
}
void ISAP(){
bfs();
max_flow=0;
while (d[s]<n){
for (int i=1;i<=n;i++) cur[i]=fi[i];
max_flow+=dfs(s,1e18);
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=m;i++){
int ss,ee;
long long dd;
scanf("%d%d%lld",&ss,&ee,&dd);
add(ss,ee,dd);
add(ee,ss,0);
}
ISAP();
printf("%lld",max_flow);
return 0;
}
易错点：建立反边的时候应该使边的下标从2开始计数，假如用异或来进行访问反边的操作的话
参考博文：
洛谷 用最通俗的语言让你学会网络流
洛谷 EK不够快？再学个Dinic吧
洛谷 究级的最大流算法：ISAP与HLPP