网络流

• 实则是根本不会记一下防止忘记
• 朗读一下本文就会背了，真的

最大流

由于鲜有点数远大于边数的图，所以我只记 Dinic。

连边

在Dinic中，我们在连边时

• 连正向边的同时连反向边
• 正向边记录反向边编号，反向边记录反向边编号。

BFS

在每次BFS中，我们处理每个点的深度。

具体的，我们让水流能流则流，也就是边权大于0就流，流的过程中记录节点深度。最终返回是否可达终点。

bool bfs(){
    for(int i=1;i<=n;i++){
        dep[i]=-1;//深度
    }
    queue<int>q;
    q.push(s);
    dep[s]=0;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(int i=0;i<g[t].size();i++){
            int ed=g[t][i].ed;
            if(dep[ed]==-1&&g[t][i].len){
                dep[ed]=dep[t]+1;//能流则流
                q.push(ed);

            }
        }
    }
    memset(cur,0,sizeof cur);//为弧优化做准备
    return (dep[t]!=-1);
}

DFS

在DFS中，我们暴力按照深度寻找若干条流。每次调用dfs只找到一条我们就返回

具体的，答案还是整数我们就一直流。

然而，有些点会在多次调用时遇到，我们加一个所谓“弧优化”，就是遍历过的点不再遍历。具体的，开一个数组存遍历到的下标即可。

有的时候会流错，答案不优，所以我们流完回溯时不仅要使正向边剪边权，还要使反向边加边权，这样她会自己流回来并回复状态。

int dfs(int st,int limit){
    if(st==t){
        return limit;
    }
    for(int i=cur[st];i<g[st].size();i++){
        cur[st]=i;
        int ed=g[st][i].ed;
        if(dep[ed]==dep[st]+1&&g[st][i].len){
            int t=dfs(ed,min(g[st][i].len,limit));
            if(t==0){
                dep[ed]=-1;
            }
            else{
                g[st][i].len-=t;
                g[ed][g[st][i].id].len+=t;
                return t;
            }
        }
    }
    return 0;
}

完整代码

/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lson now*2,l,(l+r)/2
#define rson now*2+1,(l+r)/2+1,r
#define pi pair<int,int>
#define INF 1e18
int n,m;
template<typename T>
inline void read(T &x) {
    x = 0;
    register char c = getchar();
    register short f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    x *= f;
}
template <typename T, typename... Args>
inline void read(T &x, Args &...temps)
{
    read(x), read(temps...);
}
void write(int x) {
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10;
        x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + '0');
}
int s,t;
const int N=100005,M=2e5+5;
struct E{
    int ed;
    int len;
    int id;
};
vector<E>g[N];
int dep[N],cur[N];
bool bfs(){
    for(int i=1;i<=n;i++){
        dep[i]=-1;
    }
    queue<int>q;
    q.push(s);
    dep[s]=0;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(int i=0;i<g[t].size();i++){
            int ed=g[t][i].ed;
            if(dep[ed]==-1&&g[t][i].len){
                dep[ed]=dep[t]+1;
                q.push(ed);

            }
        }
    }
    memset(cur,0,sizeof cur);
    return (dep[t]!=-1);
}
int dfs(int st,int limit){
    if(st==t){
        return limit;
    }
    for(int i=cur[st];i<g[st].size();i++){
        cur[st]=i;
        int ed=g[st][i].ed;
        if(dep[ed]==dep[st]+1&&g[st][i].len){
            int t=dfs(ed,min(g[st][i].len,limit));
            if(t==0){
                dep[ed]=-1;
            }
            else{
                g[st][i].len-=t;
                g[ed][g[st][i].id].len+=t;
                return t;
            }
        }
    }
    return 0;
}
int dinic(){
    int res=0;
    int flow=0;
    while(bfs()){
        while(flow=dfs(s,INF))res+=flow;
    }
    return res;
}
void solve()
{
    read(n,m,s,t);
    while(m--){
        int u,v,len;
        read(u,v,len);
        int sti=g[u].size();
        int edi=g[v].size();
        g[u].push_back({v,len,edi});
        g[v].push_back({u,0,sti});
    }
    cout<<dinic();
}
signed main(){
    int T=1;
    //read(T);
    while(T--){
        solve();
    }
    return 0;
}