图论（边次数限制）转流：P3163危桥
图论（边次数限制）转流：P3163危桥
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135058446
https://www.luogu.com.cn/problem/P3163
考虑一条无向边 可走 次。
我们直接这样子转换
因此直接跑即可
但此题中如果我们直接源点练出去，汇点连出入，可能会算错：
如果都能流对应的流量，那么我们把 交换也可以，这显然是充要的。
因此跑两遍即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-27
多次跑网络流（用于构造类）+霍尔定理证明可行：AGC317G
多次跑网络流（用于构造类）+霍尔定理证明可行：AGC317G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132517757 https://atcoder.jp/contests/abc317/tasks/abc317_g 一个很显然的思路，就是行向颜色连边，但约束条件展现出多个维度，所以可以考虑跑多次网络流。 但跑同样的网络流没有意义，所以每次跑完都要在残余网络上操作一下才可行。此题中，为了方便构造，就是对成功流了的边进行删除。 但多次跑网络流是否正确...
2023-11-14
缩点+图论路径网络流：1114T4
缩点+图论路径网络流：1114T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134407471 http://cplusoj.com/d/senior/p/SS231114D 重新梳理一下题目 我们先建图 x→yx\to yx→y ，然后对点分类：原串出现点，原串未出现点。 假如我们对一个原串出现点进行了操作，那么它剩余所有出边我们立刻去操作必然没有影响。所以我们只要所有原串出现点都操作一遍即可（如果有出边），那么我们就把边问题变成了点问题。 考虑一次...
2024-01-17
拆点成边来建图 +BEST定理：ABC336G
拆点成边来建图 +BEST定理：ABC336G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135658353 https://www.luogu.com.cn/problem/AT_abc336_g 考虑一个状态 (a,b,c,d)(a,b,c,d)(a,b,c,d) 要出现 kkk 次，如果相当于每次加1个字符，相当于要从 (a,b,c)(a,b,c)(a,b,c) 走到 (b,c,d)(b,c,d)(b,c,d) 走 kkk 次。因此我们就可以根据这...
2021-12-09
【SSOJ2625: 哪些路不能修】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669522.html 题目 一个有n个景点（入口）、m条单向道路的旅游胜地，单向是不友好的，因为这会让游客走很多冤枉路，而且从同一个入口出发，往不同方向走，能游玩的景点数目可能不同。于是，善良的Bob决定将道路全部改造成双向的，让每一个入口能逛的景点数量都确定下来，并制作景点数目表，让游客清楚地知道各个入口的景点数。但是，如果全部改成双向边之后，还需要修路，就可能导致景点数目表不正确。如果要景点数目表正确，请问哪些路是不能修的？ 思路 这题的...
2021-11-27
【P2194 HXY烧情侣】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15612746.html 题目链接 看题，发现是一个缩点。 缩完点后，对于每一个强连通分量，取其汽油费的最小值，最小值的和就是答案。 方案就是每个强连通分量最小值个数相乘。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071...
2023-09-16
二分套网络流：ABC320G
二分套网络流：ABC320G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132927159 首先肯定先枚举数字 然后考虑二分答案 每个字符串向它合法的位置连边 然后易发现每个点出度最多为 nnn ，不然没意义 所以最多 O(n2)O(n^2)O(n2) 条边 然后跑网络流，看能不能流完，也就是能不能匹配成功即可 123456789101112131415161718192021222324252627282930313233343536373839404...