洛谷p3376 https://www.luogu.com.cn/problem/P3376

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <cstring>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 1000000 + 5;

int n,m,be,en;

queue<int>q;

int to[maxn];

int cost[maxn];

int head[maxn];

int nex[maxn];

int cnt;

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

{

    cnt++;

    nex[cnt]=head[x];   //先把指针指向上次的位置

    head[x]=cnt;        //然后把头指向自己

    to[cnt]=y;

    cost[cnt]=z;

}

int level[maxn];

bool bfs()      //深度打表（分层）

{

    memset(level,-1,sizeof(level));

    level[be]=0;

    q.push(be);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        for(int i=head[u];i!=-1;i=nex[i])

        {

            int v=to[i];

            if(cost[i]!=0&&level[v]==-1) //流量大于0并且未被访问

            {

                level[v]=level[u]+1;

                q.push(v);

            }

        }

    }

    if(level[en]!=-1) return 1;

    else return 0;

}

int dfs(int u,int flow) //dfs找最大流    对于源点，流入它的最大流量是无限大  flow最大可行流   ret剩余可行流量

{

    if(u==en) return flow;

    int ret=flow;

    for(int i=head[u];i!=-1;i=nex[i])

    {

        if(ret<=0) break;

        int v=to[i];

        if(cost[i]!=0&&level[u]+1==level[v])

        {

            int k=dfs(v,min(ret,cost[i]));  //把能流的都给下一个点

            ret-=k;cost[i]-=k;cost[i^1]+=k;   //i^1就是反向边

        }

    }

    return flow-ret;  //最大可行流减去剩余可行流就是实际流量

}

int dinic()

{

    int ans=0;

    while(bfs()==true)   //还能分层就不断增广

    {

        ans+=dfs(be,INF);

    }

    return ans;

}

int main()

{

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

    memset(head,-1,sizeof(head));

    int x,y,z;

    cnt=-1; //从0开始 0 1 一对 2 3 一对

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

    {

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

        add(x,y,z); add(y,x,0);

    }

    printf("%d\n",dinic());

    return 0;

}