网络流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 乙津梦 @ 2019-10-30 17:38:12

@爆零_自动机 用vector存边,网络流会快很多


by xukuan @ 2019-10-30 17:40:43

@秦岭秋风 当前弧不加的话这题也是可做的


by saxiy @ 2019-10-31 17:24:24

HLPP不香嘛。。


上一页 |