利用网络流通过拆点判断图的路径存在性问题：abc318_g
利用网络流通过拆点判断图的路径存在性问题：abc318_g
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132644032
https://atcoder.jp/contests/abc318/tasks/abc318_g
对于图上一类路径是否存在问题，可以考虑网络流。
Trick1 路径存在转网络流
题目转化为：
找出两条不交路径 B->A, B->C
对于已经找到的路径，我们 不能再走 。对于当前我们找到的某条路径，我们可能进行 反悔 。这些条件列出来就是一个典型的 网络流模型 。
Trick2 无向图转网络流
考虑每个点要被流入和流出，所以可以拆成两个点。
然后流入点就向流出点连边。
其它的无向边就变成了两条有向边。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2024-01-02
Hall定理证明可行性来贪心 + 模拟断流与增流： CF1009G
Hall定理证明可行性来贪心 + 模拟断流与增流： CF1009G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135333029 https://www.luogu.com.cn/problem/CF1009G 显然是流，然后贪心，然后要每次流一下证明可行性，这里提供两种解决方法： Hall定理 左边点数只有6，我们直接 262^626 跑Hall定理 模拟断流 用EK实现网络流。我们直接少流当前位置的。显然一条流最多经过14个点，因此复杂度是对的。 H...
2023-12-19
阴阳反转——运用INF巧妙建网络流：P3980
阴阳反转——运用INF巧妙建网络流：P3980 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080814 https://vj.imken.moe/contest/598718#problem/L 考虑一个奇妙的转化： 有很多 inf\infinf 个人要走 nnn 扇门，第 iii 扇只能走 infa−i\inf_a-iinfa−i 个人，有 mmm 个通道，可以把一个人从 sis_isi 运到 ti+1t_i+1ti+1 ，但要给 c...
2023-12-19
坐标前后限制转点的坐标取值+网络流拆维拆点：agc031_e
坐标前后限制转点的坐标取值+网络流拆维拆点：agc031_e 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135075877 https://vj.imken.moe/contest/598718#problem/J 观察到数据范围很小，但一个很重要的信息我们缺失了，就是珠宝的数量，所以我们考虑枚举珠宝的数量 kkk 。 对于横纵坐标什么至多至少的限制，比如 aia_iai 前最多偷 bib_ibi 个，可以转化为第 [bi+1,k][b_i+1,k]...
2023-12-19
通过费用流中的贪心来保证计数正确性：P4249剪刀石头布
通过费用流中的贪心来保证计数正确性：P4249剪刀石头布 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080431 https://vj.imken.moe/contest/598718#problem/K 三元环数量尽量多，也就是非三元环数量尽可能少。非三元环的充要条件是存在一个点度数为2，而每条边可以给一个点一个度数，然后就变成了经典网络流问题。 但是，对于一个点，我们还是无法求最少流。考虑转化为费用流。一个点向汇点连很多条边，分别代表着度数为1...
2023-09-16
atcoder库中的网络流用法
atcoder库中的网络流用法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132643984 头文件： 12#include<atcoder/all>using namespace atcoder; 定义： 1mf_graph<int>G(N); //N为边数 连边： 1G.add_edge(u,v,w); //u->v容量为w 最大流： 1int maxflow = G.flow(S,T,1e9); //从S流向T，初始...
2023-12-18
图论（边次数限制）转流：P3163危桥
图论（边次数限制）转流：P3163危桥 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135058446 https://www.luogu.com.cn/problem/P3163 考虑一条无向边 (u,v)(u,v)(u,v) 可走 www 次。 我们直接这样子转换 因此直接跑即可 但此题中如果我们直接源点练出去，汇点连出入，可能会算错： 如果都能流对应的流量，那么我们把 s2,t2s2,t2s2,t2 交换也可以，这显然是充要的。 因此跑两遍...