dinic 10pts 点1-10MLE求助

P3376 【模板】网络最大流

暗影之梦 @ 2022-03-18 18:32:07

#include<iostream>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
        putchar(x%10+'0');
        return;
    }
    putchar(x+'0');
} 
int n,m,s,t,head[100001],cnt,dep[2001],nwb[2001];
struct edge1
{
    int to,nxt,w;
}e[100001];
void edge(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int dfs(int nw,int w)
{
    if(nw==t||w==0) return w;
    for(int &i=nwb[nw];i;i=e[i].nxt)
    {
        if(dep[e[i].to]==dep[nw]+1&&e[i].w);
        {
            int wi=dfs(e[i].to,min(w,e[i].w));
            if(wi>0)
            {
                e[i].w-=wi;
                e[i^1].w+=wi;
                return wi;
            }
        }
    }
    return 0;
}
int bfs()
{
    queue<int> q;
    memset(dep,-1,sizeof(dep));
    dep[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int nw=q.front();
        q.pop();
        for(int i=head[nw];i;i=e[i].nxt)
        {
            if(e[i].w&&dep[e[i].to]==-1)
            {
                dep[e[i].to]=dep[nw]+1;
                q.push(e[i].to);
                if(e[i].to==t) return 1;
            }
        }
    }
    return 0;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
//      cout<<114514<<endl;
        for(int i=1;i<=n;i++) nwb[i]=head[i];
        while(int ans1=dfs(s,1e16)) ans+=ans1;
    }
    return ans;
}
signed main()
{
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++) 
    {
        int u=read(),v=read(),w=read();
        edge(u,v,w);
        edge(v,u,0); 
    }
    write(dinic());
    return 0;
}

dfs和bfs出了问题但找不到,求大佬们帮忙看看


by 暗影之梦 @ 2022-03-18 18:37:05

本地运行一直没有输出,而且好像有死循环


by 「 」 @ 2022-03-18 18:51:47

@暗影之梦 你记录边的编号的 cnt0 开始了。


by Missa @ 2022-03-18 19:56:25

@暗影之梦 你还敢说你没卷?


by PosVII @ 2022-03-18 20:06:54

@暗影之梦 57行的if后面你加了个分号


by PosVII @ 2022-03-18 20:08:00

@暗影之梦 这样就会无视dep进行循环


by 暗影之梦 @ 2022-03-19 10:55:25

@PosVII 谢谢大佬


by 暗影之梦 @ 2022-03-19 10:57:55

@暗影之梦 现在它37分,WA了


by 暗影之梦 @ 2022-03-19 11:01:07

@「 」 请问您说的我的 cnt 是从零开始是在哪里啊?

这个蒟蒻没有看到在哪个地方有从0开始遍历边(眼神太不好了)


by 「 」 @ 2022-03-19 11:10:59

@暗影之梦 你的 cnt 没有赋初始值,全局变量所以是 0 ,所以你加入的一条边和其反向边可能并不是 ii^1 的关系?


by 暗影之梦 @ 2022-03-19 11:38:08

@「 」 73分,8-10RE了?


| 下一页