洛谷 3376_[模板]网络最大流

发布于 2019-05-18  11 次阅读


题目描述

如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。


#include 
#include 
#include 
#define maxn 400000
#define min(x,y) x t;
    t.push(x);
    fill(state,63);
    state[x]=0;
    while (!t.empty())
    {
        int tt=t.front();t.pop();
        for (int i=ls[tt];i;i=e[i].next)
        {
            if (e[i].w>0&&state[tt]+10)
        {
            int d=find(e[i].y,min(mn,e[i].w));
            if (d>0)
            {
                e[i].w-=d;
                e[e[i].rev].w+=d;
                return d;
            }
        }
    return 0;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&S,&E);
    for (int i=1;i<=m;i++)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
    }
    int ans=0;
    while (bfs(S))
    {
        ans+=find(S,INF);
    }
    printf("%d\n",ans);
}
]]>