网络流dinic TLE 求助

P3376 【模板】网络最大流

Lacrymabre @ 2019-10-30 16:57:06

RT,背的板子相似勿喷谢谢 一下是萌新代码,TLE 2,9,10求助

#include<bits/stdc++.h>
#define N 100001
using namespace std;

int from[N],cnt;
int net[N],to[N],v[N];
int n,m,x,y,z;
int ans,flow;
int dis[N];
queue <int> q;
int S,T;

inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    } while('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    } return x * f;
}

inline void add(int x,int y,int z)
{
    net[cnt]=from[x];
    to[cnt]=y;
    v[cnt]=z;
    from[x]=cnt++;
}

bool bfs()
{
    memset(dis,0,sizeof(dis));dis[S]=0;
    q.push(S);
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        for(int i=from[cur];i!=-1;i=net[i])
        {
            int X=to[i];
            if(dis[X]==-1&&v[i]>0)
            {
                dis[X]=dis[cur]+1;
                q.push(X);
            }   
        }
    }
    return dis[T]!=-1;
}

int dfs(int F,int exp)
{
    if(F==T) return exp;
    int flow=0,tmp=0;
    for(int i=from[F];i!=-1;i=net[i])
    {
        int X=to[i];
        if(dis[X]==dis[F]+1&&v[i]>0)
        {
            tmp=dfs(X,min(exp,v[i]));
            if(!tmp) continue;
            exp-=tmp;flow+=tmp;
            v[i]-=tmp;
            v[i^1]+=tmp;
            if(!exp) break;
        }
    }
    return flow;
}

int main()
{
    memset(from,-1,sizeof(from));
    n=read();m=read();S=read();T=read();
    for(int i=1;i<=m;i++)
    {
        x=read();y=read();z=read();
        add(x,y,z);add(y,x,0);
    }
    while(bfs()) ans+=dfs(S,0x7fffffff);
    cout<<ans;
    return 0;
}

by 传奇666666 @ 2019-10-30 16:59:11

大哥,你不觉得开反向边就需要两倍的边数了吗?还只开一倍的空间。


by Lacrymabre @ 2019-10-30 16:59:42

@传奇666666 !我试试


by Lacrymabre @ 2019-10-30 17:01:03

@传奇666666 现在全部TLE了


by Lacrymabre @ 2019-10-30 17:01:11

继续求助


by 乙津梦 @ 2019-10-30 17:07:07

用vector啊


by Uniecho1 @ 2019-10-30 17:08:22

@爆零_自动机 不加当前弧优化时间复杂度是假的...


by Lacrymabre @ 2019-10-30 17:09:08

@缘生艺转 不会awa


by Lacrymabre @ 2019-10-30 17:09:24

@秦岭秋风 也就是说要加优化???


by CreeperLordVader @ 2019-10-30 17:09:57

@爆零_自动机 可能是队列没清空吧

队列最好开在函数里


by Uniecho1 @ 2019-10-30 17:11:44

@爆零_自动机 嗯是的(虽然我都是好久以前做的这个题了)


| 下一页