啊,网络流

P3376 【模板】网络最大流

shitbro @ 2019-09-30 14:06:25

DINIC 未知错误???无法输出

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=1<<30;
int n,m,s,t;
int cnt=1,maxflow=0;
int head[100005],dep[100005],inque[100005];
struct node{
    int last,to,val;
}tree[100005];
void add(int x,int y,int z)
{
    tree[++cnt].last=head[x];
    tree[cnt].to=y;
    tree[cnt].val=z;
    head[x]=cnt;
}
bool D_pre()
{
    memset(dep,0x3f,sizeof dep);
    memset(inque,0,sizeof inque);
    dep[s]=0;
    queue <int> q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(int i=head[u];i;i=tree[i].last)
        {
            int d=tree[i].to;
            if(dep[d]>dep[u]+1&&tree[i].val)
            {
                dep[d]=dep[u]+1;
                if(!inque[d])
                {
                    q.push(d);
                    inque[d]=1;
                }
            }
        }
    }
    if(dep[t]!=0x3f3f3f3f)
    return 1;
    return 0;
}
int D_dfs(int u,int flow)
{
    int low=0;
    if(u==t)
    {
        maxflow+=flow;
        return flow;
    }
    int used=0;
    for(int i=head[u];i;i=tree[i].last)
    {
        int d=tree[i].to;
        if(tree[i].val&&dep[d]==dep[u+1])
        {
            if(low=D_dfs(d,min(flow-used,tree[i].val)))
            {
                used+=low;
                tree[i].val-=low;
                tree[i^1].val+=low;
                if(used==flow)
                break;
            }
        }
    }
    return used;
}
int dinic()
{
    while(D_pre())
    {
        D_dfs(s,inf);
    }
    return maxflow;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
    }
    printf("%d",dinic());
    return 0;
} 

by bellmanford @ 2019-09-30 14:14:47

@larry❤DVA 好像这是EK吧


by shitbro @ 2019-09-30 14:16:14

@bellmanford
是dinic
是多路增广


by shitbro @ 2019-09-30 14:16:59

@142857cs


by shitbro @ 2019-09-30 14:17:45

@142857cs au爷求助


by shitbro @ 2019-09-30 14:20:46

有人吗????


by bellmanford @ 2019-09-30 14:22:36

神奇,我打网络流用EK的bfs和Dinic的dfs都在这

吐槽而已QwQ


by shitbro @ 2019-09-30 14:26:24

@bellmanford bfs是找是否有增广路 dfs是处理


by bellmanford @ 2019-09-30 14:32:44

只是吐槽啦


by 辰星凌 @ 2019-09-30 15:25:33

if(tree[i].val&&dep[d]==dep[u+1])

改为dep[d]==dep[u]+1


by 辰星凌 @ 2019-09-30 15:26:05

@辰星凌 漏了,是if(tree[i].val&&dep[d]==dep[u]+1)


| 下一页