求助dalao dalao往这看 thanks

P3376 【模板】网络最大流

dChengx @ 2020-01-22 22:55:25

求助蒟蒻!!!

重打模板,TLE飞了

#include<bits/stdc++.h>
#define N 10005
#define M 200005 
using namespace std;
const int inf=1e9;
int n,m,cnt=1,maxflow,d[N],S,T;
int ver[M],nx[M],v[M],fi[N];
queue<int> q;

void add(int x,int y,int z){
    ver[++cnt]=y;nx[cnt]=fi[x];fi[x]=cnt;v[cnt]=z;
}

bool bfs(){
    memset(d,0,sizeof(d));
    q.push(S);
    d[S]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=fi[x];i;i=nx[i])
            if(!d[ver[i]]&&v[i]){
                int y=ver[i];
                d[y]=d[x]+1;
                q.push(y);
                if(y==T)return 1;
            }
    }
    return 0;
}

int dfs(int x,int flow){
    if(x==T||!flow)return flow;
    int ans,res=flow;
    for(int i=fi[x],y=ver[i];i&&res;i=nx[i])
        if(v[i]&&d[y]==d[x]+1){
            ans=dfs(y,min(flow,v[i]));
            if(!ans)d[y]=0;
            v[i]-=ans;
            v[i^1]+=ans;
            res-=ans;
            if(!res)return flow;
        }
    return flow-res;
}

void dinic(){
    while(bfs())maxflow+=dfs(S,inf);
}

int main(){
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i=1;i<=m;i++){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(b,a,0);
    }
    dinic();
    printf("%d",maxflow);
    return 0;
}

by dChengx @ 2020-01-22 22:56:32

后来我又去蓝书上面找,这是我借鉴完蓝书之后的代码。。。

9TLE 1WA


by Wyxrg @ 2020-01-23 08:04:51

%%%


by Wyxrg @ 2020-01-23 08:48:30

看不出来诶

我好菜啊


by dChengx @ 2020-01-23 20:47:36

我更菜。。。


by dChengx @ 2020-01-23 21:19:29

我知道我哪错了

dinic函数里面与dfs里面有一个地方矛盾了:

if(!ans)d[y]=0;

原来这边是为了剪枝的

但是做完一遍dfs之后直接bfs了(在我的程序里)

所以剪枝无意义

所以从原来的dfs:

int dfs(int x,int flow){
    if(x==T||!flow)return flow;
    int ans,res=flow;
    for(int i=fi[x],y=ver[i];i&&res;i=nx[i])
        if(v[i]&&d[y]==d[x]+1){
            ans=dfs(y,min(flow,v[i]));
            if(!ans)d[y]=0;
            v[i]-=ans;
            v[i^1]+=ans;
            res-=ans;
            if(!res)return flow;
        }
    return flow-res;
}

变为

int dfs(int x,int flow){
    if(x==t)return flow;
    int now;
    for(int i=fi[x];i;i=nx[i]){
        int y=ver[i];
        if(dep[y]!=dep[x]+1)continue;
        now=dfs(y,min(flow,v[i]));
        if(now){
            v[i]-=now;
            v[i^1]+=now;
            return now;
        }
    }
    return 0;
}

但本蒟蒻还有一个问题

就是这里

if(now){
    v[i]-=now;
    v[i^1]+=now;
    return now;
}

这里直接返回答案确实没问题(有残余网络的话,bfs会判定的)

但为什么直接返回就不TLE了

求助dalao


by dChengx @ 2020-11-15 16:36:14

刚刚又了一遍Dinic,貌似它一次dfs要增广多条路


|