关于对Dinic算法的理解

WanderOvO @ 2020-07-17 10:53:46

by WanderOvO @ 2020-07-17 10:54:00

第二天学网络流，不知道理解得对不对

by Haishu @ 2020-07-17 11:04:26

@BUAA_Wander 你贴个代码吧，因为我最近发现我写了多年的dinic是单路增广而不是我想象当中的多路增广/kk

by WanderOvO @ 2020-07-17 11:07:51

@Hygebra hh，蒟蒻还没写出来代码，我先把引发我思考的放出来吧

by WanderOvO @ 2020-07-17 11:14:22

@Hygebra 蒟蒻斗胆认为对于一份AC的Dinic算法的代码，区分是单路还是多路只需要看它是

while(bfs()){
    ll ret=0;
    while((ret=dfs())!=0){ //一次bfs需要多次dfs修改边权
        ans+=ret;
    }
} //参数缺省了，意会就好

还是

while(bfs()){
    ans+=dfs();
}

就好了

by AzusaCat @ 2020-07-17 11:57:12

@BUAA_Wander 不是这样的吧/jk

by WanderOvO @ 2020-07-17 14:47:16

@S1rius 那请问应该怎么考虑EK和Dinic之间的关系呢（不懂就问）

by AzusaCat @ 2020-07-17 14:57:14

@BUAA_Wander EK是记个前驱一次只增广一条路吧