最大流dinic板子

题目： https://www.luogu.com.cn/problem/P3376

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int INF=0x7fffffff;
typedef long long ll;
int n,m,s,t;
int head[MAXN<<1],tot;
struct node
{
    int to,nxt,flow;
}e[MAXN<<1];
void add(int x,int y,int z)
{
    e[tot].to=y;e[tot].nxt=head[x];e[tot].flow=z;head[x]=tot++;
}
void add_edge(int x,int y,int z)
{
    add(x,y,z);add(y,x,0);
}
ll deep[MAXN],tail,be,q[MAXN];
bool bfs()
{
    memset(deep,0,sizeof(deep));
    deep[s]=1;
    ll be=0,tail=1;
    q[1]=s;
    while(be!=tail)
    {
        ll u=q[++be];
        for(int i=head[u];~i;i=e[i].nxt)
        {
            if(!deep[e[i].to]&&e[i].flow)
            {
                deep[e[i].to]=deep[u]+1;
                q[++tail]=e[i].to;
            }
        }
    }
    return deep[t];
}
int dfs(int now,int fa1)
{
    if(now==t)return fa1;
    int fa=0;
    for(int i=head[now];~i&&fa1;i=e[i].nxt)
    {
        if(deep[e[i].to]==deep[now]+1&&e[i].flow)
        {
            int d=dfs(e[i].to,min(fa1,e[i].flow));
            if(d>0)
            {
                e[i].flow-=d;
                e[i^1].flow+=d;
                fa1-=d;
                fa+=d;
            }
        }
    }
    if(!fa)deep[now]=-1;
    return fa;
}
ll dinic()
{
    ll res=0;
    while(bfs())
    {
        res+=dfs(s,INF);
    }
    return res;
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
    }
    int ans=dinic();
    printf("%d
",ans);
    return 0;
}