网络流模板 dinic

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int maxn=1e5+10;
const int maxe=4e5+10;
const int inf=0x3f3f3f3f;

queue <int> q;
int dis[maxn],n,m,s,t,cnt,ls[maxn],ans;
struct edge
{
    int to,c,op,next;
}e[maxe];

void add(int x,int y,int w)
{
    e[++cnt]=(edge){y,w,cnt+1,ls[x]};
    ls[x]=cnt;
    e[++cnt]=(edge){x,0,cnt-1,ls[y]};
    ls[y]=cnt;
}

bool bfs()
{
    memset(dis,inf,sizeof(dis));
    while (!q.empty()) q.pop();
    q.push(s);
    dis[s]=0;
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        for (int i=ls[x];i;i=e[i].next)
        {
            int y=e[i].to;
            if (e[i].c&&dis[y]>dis[x]+1)
            {
                dis[y]=dis[x]+1;
                if (y==t) return 1;
                q.push(y);
            }
        }
    }
    return 0;
}

int dfs(int x,int maxf)
{
    if (x==t) return maxf;
    int ret=0;
    for (int i=ls[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if (e[i].c&&dis[y]==dis[x]+1)
        {
            int f=dfs(y,min(e[i].c,maxf-ret));
            if (!f) dis[y]=-1;
            e[i].c-=f;
            e[e[i].op].c+=f;
            ret+=f;
            if (ret==maxf) break;
        }
    }
    return ret;
}

int dinic()
{
    int flow=0;
    while (bfs())
        ans+=dfs(s,inf);
    return ans;
}

int main ()
{
     cin>>n>>m>>s>>t;
     for (int i=1,x,y,w;i<=m;i++)
     {
         cin>>x>>y>>w;
         add(x,y,w);
     }
     ans=dinic();
     cout<<ans;
}