学习笔记目录
有任何问题，欢迎私信/评论。
码字不易，求点赞啦~

最大流问题

求一个网络中，最多能有多少个单位的流量能从源点流向汇点。————这就是最大流问题。

求解最大流问题有两大主要算法：$EK$ 算法和 $dinic$ 算法。

$EK$ 算法

$EK$ 算法也叫动能算法（$E_K$）。

利用一下贪心的思想，可以发现：只要残量网络中存在增广路，流量就可以增大；如果残量网络中已经没有增广路了，那么当前求得的流就是最大流。这个就是著名的 增广路定理。

$EK$ 算法就利用了增广路定理，每次 $bfs$ 会沿着最短增广路（也就是边数最少的增广路）进行增广。那么这一条增广路对答案的贡献就是所有弧上残量的最小值。

记这当前增广路所有弧上残量的最小值为 $mn$。那么需要把正向弧的残量减去 $mn$，反向弧的流量加上 $mn$。

$EK$ 算法代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=200;                             //点数 
const int maxm=400;                             //边数（由于有反向弧，所以要乘以2，具体数值看题目的数据范围） 
const long long inf=0x3f3f3f3f;

struct edge {
    int fr,to,nxt;
    long long c;                                //一条边的流量 
}e[maxm];
int n,m,s,t;
int cnt=1;
int head[maxn];

void add_edge(int u,int v,long long c){
    cnt++;
    e[cnt].fr=u;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].c=c;
    head[u]=cnt;
}

int pre[maxn];

void bfs(){                                     //bfs 寻找一条最短增广路 
    queue<int>q;
    q.push(s);
    memset(pre,-1,sizeof(pre));
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(pre[v]==-1 && e[i].c){
                pre[v]=i;
                if(v==t){
                    break;
                }
                q.push(v);
            }
        }
        if(pre[t]!=-1){
            break;
        }
    }
}

long long EK(){                                 //将 bfs 中找到增广路上的所有流量进行修改 
    long long ret=0;
    while(1){
        bfs();
        if(pre[t]==-1){
            break;
        }
        long long Min_c=inf;
        for(int u=t;u!=s;u=e[pre[u]].fr){
            Min_c=min(Min_c,e[pre[u]].c);       //找出所有弧中的最小流量 
        }
        for(int u=t;u!=s;u=e[pre[u]].fr){
            e[pre[u]].c-=Min_c;                 //正向弧减去最小流量 
            e[pre[u]^1].c+=Min_c;               //反向弧加上最小流量。这里利用了奇数^1=偶数，偶数^1=奇数的原理，能够保证(2,3)(3,4)等组成一组。 
        }
        ret+=Min_c;
    }
    return ret;
}

int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v;
        long long flow;
        cin>>u>>v>>flow;
        add_edge(u,v,flow);
        add_edge(v,u,0);
    }
    cout<<EK()<<endl;
    return 0;
}

$dinic$ 算法

$dinic$ 算法与 $EK$ 算法类似，也是不停的寻找增广路。但是 $EK$ 算法是一条一条地找增广路，效率太过低下。$dinic$ 算法会利用分层的思想，一次性找出多条增广路（注意不是所有），提高效率。

1. $dinic$ 算法会构建分层图，按照层次关系增广。每一次对源点进行 $bfs$，对每个节点按照层次编号。

2. $dfs$ 进行多路增广。$EK$ 算法一次只会增广一条路径，$dinic$ 通过 $dfs$ 能同时找到多条增广路。
   为什么需要进行分层？

分层，就能够流量只会从低层次的节点往高层次的节点走（也就是相邻的两层），而不会出现回流的情况。因为一旦回流，$dfs$ 就会陷入死循环。

$dinic$ 算法代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=205;
const int maxm=5005;
const long long inf=50010000000000;

int n,m,s,t;

struct edge{
    int fr,to,nxt;
    long long c;
}e[maxm<<1];
int head[maxn],cnt=1;
int dep[maxn];//dep[u] 代表节点 u 所在的层 
int q[maxn],l,r;

void add_edge(int u,int v,int c){
    cnt++;
    e[cnt].fr=u;
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].c=c;
    head[u]=cnt;
}

bool bfs(){
    l=1; r=0;
    q[++r]=s;
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    while(l<=r){
        int u=q[l];
        l++;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].c>0 && dep[v]==0){//如果一条边还有流量，且点未被分层，就需要将他分层 
                q[++r]=v;
                dep[v]=dep[u]+1;
            }
        }
    }
    if(dep[t]==0) return false;
    return true;
}

long long dfs(int u,long long flow){
    if(u==t) return flow;
    long long tot=0;
    for(int i=head[u];i && flow;i=e[i].nxt){
        int v=e[i].to;
        if(e[i].c>0 && dep[v]==dep[u]+1){
            long long res=dfs(v,min(flow,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            tot+=res;
            flow-=res;
            if(flow==0){
                break;
            }
        }
    }
    if(tot==0){
        dep[u]=0;
    }
    return tot;
}

long long dinic(){
    long long ret=0;
    while(bfs()){
        ret+=dfs(s,inf);
    }
    return ret;
}

int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,c;
        cin>>u>>v>>c;
        add_edge(u,v,c);
        add_edge(v,u,0);
    }
    cout<<dinic()<<endl;
    return 0;
}