图论（边次数限制）转流：P3163危桥

2023-12-18 14:33:41

https://www.luogu.com.cn/problem/P3163

考虑一条无向边 ( u , v ) (u,v) (u,v) 可走 w w w 次。
在这里插入图片描述

我们直接这样子转换

在这里插入图片描述

因此直接跑即可

但此题中如果我们直接源点练出去，汇点连出入，可能会算错：

在这里插入图片描述

如果都能流对应的流量，那么我们把 s 2 , t 2 s2,t2 s2,t2 交换也可以，这显然是充要的。

在这里插入图片描述

因此跑两遍即可。

文章来源:https://blog.csdn.net/zhangtingxiqwq/article/details/135058446
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。