Dinic730ms

P3376 【模板】网络最大流

Harukawa @ 2021-11-23 18:45:30

尝试了若干次，发现速度依然很慢，去看了其他ac的代码，暂且没能发现问题，可能是当前弧优化的问题（？？），代码如下，还望不吝赐教

#include <bits/stdc++.h>
#define ll long long
#define rint register int 
#define gc getchar
#define inf 200011230000
#define maxm 12000
#define maxn 400
using namespace std;

inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
    for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
    for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
    return sgn-'-'?ans:-ans;
}

struct Edge{
    ll to,val;
    Edge(ll t=0L,ll v=0L):to(t),val(v){}
}ed[maxm+20];
int he[maxn+20],now[maxn+20],ne[maxm+20],dep[maxn+20],maxint[maxn+20];
int tot=1,n,m,s,t,u,v;
ll w,ans;

void add_edge(int f,int t,ll v){
    ed[++tot]=Edge(t,v);
    ne[tot]=he[f];
    he[f]=tot;
}

bool bfs(int s){
    memcpy(now,he,sizeof(now));
    memcpy(dep,maxint,sizeof(dep));
    queue<int> q;
    q.push(s);
    dep[s]=1;
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        if(tmp==t) return true;
        for(rint i=he[tmp];i;i=ne[i]){
            if(dep[ed[i].to]==2147483647&&ed[i].val>0){
                dep[ed[i].to]=dep[tmp]+1;
                q.push(ed[i].to);
            }
        }
    }
    return false;
}

ll dfs(int o,ll in){
    if(o==t) return in;
    ll k,out=0;
    for(rint i=now[o];i;i=ne[i]){
        now[o]=i;
        if(dep[ed[i].to]==dep[o]+1&&ed[i].val>0){
            k=dfs(ed[i].to,min(in,ed[i].val));
            ed[i].val-=k;
            ed[i^1].val+=k;
            in-=k;
            out+=k;
            if(ed[i].val==0) dep[ed[i].to]=2147483647;
        }
    }
    return out;
}

int main(){
    cin>>n>>m>>s>>t;
    for(rint i=0;i<maxn;i++) maxint[i]=2147483647;
    for(rint i=1;i<=m;i++){
        u=read();
        v=read();
        w=read();
        add_edge(u,v,w);
        add_edge(v,u,0L);
    }
    while(bfs(s)) ans+=dfs(s,inf);
    cout<<ans;
    return 0;
}

by jiangtaizhe001 @ 2021-11-23 19:03:26

在 dfs 的 for 循环的地方加一句 if(!in) break;

by Guoyh @ 2021-11-23 19:03:28

@Mikoto_lin dfs里面in减到0了就要退出

by fzj2007 @ 2021-11-23 19:12:07

@Mikoto_lin 你这样写优化就假了，每次都会遍历全，然后bfs了很多次

by Harukawa @ 2021-11-23 19:15:57

@jiangtaizhe001 谢谢提醒。我改正之后是280ms，这差不多是dinic的正常速度吗？

by Harukawa @ 2021-11-23 19:17:42

@Guoyh 我明白了，谢谢，写的时候没有考虑好。改正之后是280ms，请问dinic这个速度能到平均线吗

by Harukawa @ 2021-11-23 19:18:22

@fzj2007 谢谢提醒，我明白了

by jiangtaizhe001 @ 2021-11-23 19:46:13

好像我的 dinic 貌似是 40多ms。。
估计是 bfs 的差别吧（？）。

queue<int> q,E;
int dep[maxn],now[maxn];
int bfs(){
    for(int i=1;i<=n;i++) dep[i]=0,now[i]=head[i];
    q=E; q.push(s); dep[s]=1;
    while(!q.empty()){
        int cur=q.front(); q.pop();
        for(int i=head[cur];i;i=nex[i])
            if(c[i]>0&&!dep[to[i]]){
                dep[to[i]]=dep[cur]+1;
                if(to[i]==t) return 1;
                q.push(to[i]);
            }
    }
    return 0;
}

by zhy137036 @ 2021-11-23 19:54:24

@Mikoto_lin 不大正常

https://www.luogu.com.cn/record/62982559

by 望月Asta @ 2021-11-23 20:35:19

@Mikoto_lin

没多路增广.
循环里没特判 in = 0.
别用memcpy(),因为增广到最后残量网络上不是每个结点都能走到的.
只论这道题的话 Dinic 标准时间为少于100ms,使劲卡常能卡到 26ms.

by Harukawa @ 2021-11-23 22:25:38

首先感谢楼上各位，但我现在依旧卡在了200ms左右，其中9和10号点均在100ms左右，其他点正常代码和测试信息

加入了in=0的特判，并且没有使用memcpy，参考了许多代码，但是并没有找到具体的问题，导致现在比较困扰。不知道有没有办法得到这两组测试数据？或者能看出我的代码还有什么问题（我真的脑子转不动了好崩溃）。

#include <bits/stdc++.h>
#define ll long long
#define rint register int 
#define gc getchar
#define inf 200011230000
#define maxm 12000
#define maxn 400
using namespace std;

inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc()){
    for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
    for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
    return sgn-'-'?ans:-ans;
}

struct Edge{
    ll to,val;
    Edge(ll t=0L,ll v=0L):to(t),val(v){}
}ed[maxm+20];
int he[maxn+20],now[maxn+20],ne[maxm+20],dep[maxn+20],maxint[maxn+20];
int tot=1,n,m,s,t,u,v;
ll w,ans;

void add_edge(int f,int t,ll v){
    ed[++tot]=Edge(t,v);
    ne[tot]=he[f];
    he[f]=tot;
}

bool bfs(int s){
    for(rint i=1;i<=n;i++) now[i]=he[i],dep[i]=-1;
    queue<int> q;
    q.push(s);
    dep[s]=1;
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        for(rint i=he[tmp];i;i=ne[i]){
            if(dep[ed[i].to]==-1&&ed[i].val>0){
                dep[ed[i].to]=dep[tmp]+1;
                if(ed[i].to==t) return true;
                q.push(ed[i].to);
            }
        }
    }
    return false;
}

ll dfs(int o,ll in){
    if(o==t) return in;
    ll k,out=0;
    for(rint i=now[o];i;i=ne[i]){
        now[o]=i;
        if(dep[ed[i].to]==dep[o]+1&&ed[i].val>0){
            k=dfs(ed[i].to,min(in,ed[i].val));
    //      if(k==0) dep[v]=-1;
            ed[i].val-=k;
            ed[i^1].val+=k;
            in-=k;
            out+=k;

            if(ed[i].val==0) dep[ed[i].to]=-1;
            if(in==0) break;
        }
    }
    return out;
}

int main(){
    cin>>n>>m>>s>>t;
    for(rint i=1;i<=m;i++){
        u=read();
        v=read();
        w=read();
        add_edge(u,v,w);
        add_edge(v,u,0L);
    }
    while(bfs(s)) ans+=dfs(s,inf);
    cout<<ans;
    return 0;
}

加上那句注释甚至会TLE

| 下一页