先摆上网络流的经典问题  ：给你一个图，每条边表示能过通过这条变的最大流量，问你从源点最多流多少到终点
然后介绍增广路算法：每次选一条从起点到终点的路径，并且答案ans加上这条路径的最小值，并且反向建边，权值为流过的花费，至于反向建边的意义看这个图吧

EK算法：用bfs跑最短路，然后dfs找最小值
dinic优化： 首先了解下分层图的概念 从起点到终点路径相同的点如{1,2,4},{1,3,4} 。优化时用dfs遍历所有相同层的图直到找不到路径了就退出去找找下一层的图
时间复杂度分析（百度词条）：因为在Dinic的执行过程中，每次重新分层，汇点所在的层次是严格递增的，而n个点的层次图最多有n层，所以最多重新分层n次。在同一个层次图中，因为每条增广路都有一个瓶颈，而两次增广的瓶颈不可能相同，所以增广路最多m条。搜索每一条增广路时，前进和回溯都最多n次，所以这两者造成的时间复杂度是O(nm)；而沿着同一条边(i,j)不可能枚举两次，因为第一次枚举时要么这条边的容量已经用尽，要么点j到汇不存在通路从而可将其从这一层次图中删除。综上所述，Dinic算法时间复杂度的理论上界是O(n^2*m)。
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+5;
const int INF=0x3f3f3f3f;
struct Node{
    int to,ne,w;
}e[MAX];
int head[MAX],dis[MAX];
int n,m,s,t,cnt;
queue<int>que;
void init(){
    while(!que.empty()) que.pop();
    cnt=0;
    memset(head,-1,sizeof head);
}
void add(int u,int v,int w){//链式前向星建图
    e[cnt].ne=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt++;
}
int bfs(){
    memset(dis,0,sizeof dis);
    que.push(s);
    dis[s]=1;
    while(!que.empty()){
        int v=que.front();
        que.pop();
        for(int i=head[v];~i;i=e[i].ne){
            if(e[i].w>0&&dis[e[i].to]==0){
                que.push(e[i].to);
                dis[e[i].to]=dis[v]+1;
            }
        }
    }
    if(dis[t]==0) return 0;//是否联通
    else return 1;
}
int dfs(int u,int val){
    if(u==t){
        return val;
    }
    for(int i=head[u];~i;i=e[i].ne){
        if(dis[e[i].to]==dis[u]+1&&e[i].w>0){
            int va=dfs(e[i].to,min(val,e[i].w));
            if(va!=0){
                e[i].w-=va;
                e[i^1].w+=va;
                return va;
            }
        }
    }
    return 0;
}
int dinic(){
    int ans=0;
    while(bfs()){
        int cc;
        while(cc=dfs(s,INF))ans+=cc;//dinic优化，遍历所有bfs跑出来的全部最短路
    }
    return ans;
}
int main(){
//    freopen("1.txt","r",stdin);
    cin>>n>>m>>s>>t;
    init();
    for(int i=0;i<m;i++){
        int u,v,val;
        cin>>u>>v>>val;
        add(u,v,val);
        add(v,u,0);
    }
    cout<<dinic()<<endl;
}