关于Dinic

P3376 【模板】网络最大流

Anduin_Urien @ 2023-11-13 21:42:13

inline long long dfs(int u,long long flow){
    if(!flow||u==t) return flow;
    long long now=flow;
    for(register int i=p[u];i&&now;i=e[i].next){
        int v=e[i].to; long long fl=e[i].val;
        p[u]=i;
        if(!fl||d[v]!=d[u]+1) continue;
        long long k=dfs(v,Min(now,fl));
        e[i].val-=k; e[i^1].val+=k; now-=k;
    }
    return flow-now;
}

这段代码里的flow是什么意思啊(复习网络流的时候脑子抽了想不起来了)


by Anduin_Urien @ 2023-11-13 21:43:00

while(bfs()) ans+=dfs(s,inf);

main函数里是这么调用的


by liangbowen @ 2023-11-13 21:44:53

当前调用 dfs() 时的最大流量


by Anduin_Urien @ 2023-11-13 21:48:05

@liangbowen thx,那么now久应该是当前的剩余流量是吧,所以最后的实际流量就应该是flow-now


by OIer_FY @ 2023-11-15 21:15:02

@Anduin_Urien 1,for 哪里不要忘记写 now 哦(多次寄在这里)


by Anduin_Urien @ 2023-11-16 11:57:58

@OIer_FY thx,此贴结


|