dinic蜜汁TLE 82pts求助

houpingze @ 2021-06-17 21:34:07

by Vincula @ 2021-06-17 21:43:41

int dinic(int x,int w){//x 当前点 w 流量
    int sum=0;
    if(x==t) return w;
    for(int i=hd[x];i&&w;i=G[i].nxt){
        int u=x,v=G[i].x;
        if(G[i].w&&vis[u]+1==vis[v]){
            int k=dinic(v,min(w,G[i].w));
            w-=k;
            sum+=k;
            G[i].w-=k,G[i^1].w+=k;
        }
    }
    if(!sum) vis[x]=0;
    return sum;
}

这题裸的dinic过不了

by SIXIANG32 @ 2021-06-17 21:43:58

@houpingze 不加当前弧优化，邪教！

by Vincula @ 2021-06-17 21:44:08

@houpingze

by Stinger @ 2021-06-17 21:47:22

@houpingze w=0 要及时退出，改了91pts；

加了当前弧100pts。

代码见https://www.luogu.com.cn/paste/q6txjeuq

by SIXIANG32 @ 2021-06-17 21:52:36

@houpingze 还有循环的时候要判断 w 是不是 = 0，w = 0 直接退出

by houpingze @ 2021-06-17 21:55:39

啊这么多人帮我调代码啊，太感动了/kel

那我就在群里发个红包把（）

by cyffff @ 2021-06-18 12:36:06

裸 dininc 可以过啊