初学最大流求助正确性

P3376 【模板】网络最大流

_LanFeng_ @ 2024-09-01 10:32:31

按照算法导论学的，其推导非常严谨，但是要求网络没有反向边（若(u,v)∈E，则(v,u)∉E）；如果有反向边的图，则要增加一个新点进行等价转化（若(u,v)∈E且(v,u)∈E，则添加一个新点p，忽略(v,u)并加上(v,p),(p,u)两条边）；但是这个转化为什么在代码里面没有体现呢？

by _LanFeng_ @ 2024-09-01 22:04:15

@Stairs_upon_temple 黑色的边是原来的图就有的边，红色的边是残存网络添加的反向边

by Stairs_upon_temple @ 2024-09-02 09:05:57

@LanFeng 正确的，其实不止是FF，对于任意的基于增广路的最大流算法（应该是的）都可以通过该思想进行转换，还有我建议你学一下dinic,基本上只要不卡，网络流的题都能过（除了预流推进的模板应该没有哪道题会去卡dinic）

%%%~~大佬对网络流的理解已经远超于我了~~

by _LanFeng_ @ 2024-09-02 23:17:21

@Stairs_upon_temple 我今天学了dinic哈哈。谢谢您的回复，感谢您的解惑，真是对我这种自学选手莫大的帮助！已经关注您啦

上一页 |