洛谷 IDE 都AC了,为什么交上去 TLE 爆零

P3376 【模板】网络最大流

__vector__ @ 2022-07-11 13:05:31

RT.调了 2h,无果。把数据下载到本地,用洛谷 ide 跑了一遍,居然 AC,我不知道这是为什么

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    ll inf=1e17;
    const int maxn=205;
    const int maxm=5005;
    int n,m,s,t;
    struct EDGE
    {
        int to,nxt;
        ll val;
    }edge[maxm<<1];
    int cnt;
    int head[maxn];
    inline void add(int u,int to,ll val)
    {
        edge[++cnt].to=to;
        edge[cnt].val=val;
        edge[cnt].nxt=head[u];
        head[u]=cnt;
    }
    int dep[maxn];
    bool inq[maxn];
    inline bool bfs()
    {
        for(int i=0;i<maxn;i++)dep[i]=inf;
        memset(inq,0,sizeof(dep));
   //     cout<<dep[t]<<endl;
        queue<int> q;
        dep[s]=0;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            inq[u]=0;
            for(int i=head[u];i;i=edge[i].nxt)
            {
                int to=edge[i].to;
                if(edge[i].val&&dep[to]>dep[u]+1)
                {
                    dep[to]=dep[u]+1;
                    if(!inq[to])
                    {
                        inq[to]=1;
                        q.push(to);
                    }
                }
            }
        }
        if(dep[t]<0x3f3f3f3f)return 1;
        return 0;
    }
    ll dfs(int u,ll imin)
    {
        if(u==t)return imin;
        ll e_val=0;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(!edge[i].val||(dep[u]+1!=dep[to]))continue;
            if(e_val=dfs(to,min(edge[i].val,imin)))
            {
                if(i&1)
                {
                    edge[i].val-=e_val;
                    edge[i+1].val+=e_val;
                }
                else
                {
                    edge[i].val-=e_val;
                    edge[i-1].val+=e_val;
                }
                return e_val;
            }
        }
        return 0;
    }
    inline void Dinic()
    {
        ll ans=0;
        while(bfs())
        {
            ll imin;
            while(imin=dfs(s,inf))ans+=imin;
        }
        printf("%lld",ans);
    }
    void main()
    {
        scanf("%d%d%d%d",&n,&m,&s,&t);
        int u,v;
        ll w;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%lld",&u,&v,&w);
            add(u,v,w);
            add(v,u,0);
        }
        Dinic();
    }
}
int main()
{
    Main::main();
    return 0;
}

by __vector__ @ 2022-07-11 13:12:47

谁调出来了,3 个关注


by hy233 @ 2022-07-11 13:44:58

洛谷IDE样例能过不代表能AC吧


by hy233 @ 2022-07-11 13:48:20

@vector

memset(inq,0,sizeof(dep));

???


by __vector__ @ 2022-07-11 13:49:12

@hy233


by __vector__ @ 2022-07-11 13:49:33

@hy233 好,3 个关注这就给你


by hy233 @ 2022-07-11 13:50:28

inq[u]=0;

你这随便来个环你就寄了啊


by hy233 @ 2022-07-11 13:52:02

为什么dfs里面直接return了啊


by hy233 @ 2022-07-11 13:52:29

@vector


|