网络最大流dinic模板

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

queue<int>q;

int INF=1e9;

int n,m,head[],cur[],ct=,s,t,d[],ans;

struct N{

    int to,next,w;

}edge[];

void add(int x,int y,int z)

{

    edge[++ct]=(N){y,head[x],z};head[x]=ct;

    edge[++ct]=(N){x,head[y],};head[y]=ct;

}

bool bfs()

{

    memset(d,,sizeof d);

    while(q.size())q.pop();

    d[s]=;

    q.push(s);

    while(q.size())

    {

        int x=q.front();q.pop();

        for(int i=head[x];i;i=edge[i].next)

        {

            int u=edge[i].to;

            if(!d[u]&&edge[i].w)//残量网络

            {

                d[u]=d[x]+;

                q.push(u);

            }

        }

    }

    return d[t];

}

int dfs(int x,int f)

{

    if(x==t)return f;//

    int res=,tmp=;

    for(int i=cur[x];i;i=edge[i].next)

    {

        int u=edge[i].to;

        if(d[u]==d[x]+&&edge[i].w)

        {

            tmp=dfs(u,min(edge[i].w,f-res));

            edge[i].w-=tmp;

            edge[i^].w+=tmp;

            res+=tmp;

            if(edge[i].w)cur[x]=i;

            if(res==f)return f;//

        }

    }

    if(!res)d[x]=;//剪枝

    return res;

}

int main()

{

    scanf("%d%d",&n,&m);

    scanf("%d%d",&s,&t);

    int x,y,z;

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

    }

    while(bfs())

    {

        for(int i=;i<=n;i++)cur[i]=head[i];

        ans+=dfs(s,INF);

    }

    printf("%d",ans);

    return ;

}