分析性质+上下界网络流：CodeForces - 1416F
分析性质+上下界网络流：CodeForces - 1416F
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135069614
https://vj.imken.moe/contest/598718#problem/E
分析一波性质，一个位置旁边有比他小的那没问题，如果没有只能找朋友了。
找朋友，也就是形成环，由于每次只能上下左右，所以必然是个偶环。我们直接全部拆成二元环，因为一定可以拆。二元环，就可以匹配了。
但有些点可能旁边有比他小，但他也要拿去匹配，但他不一定一定需要被匹配。关于此，也就是一些点一定要被匹配，一些不一定，我们可以建个上下界网络流来解决（有源汇）。
本博客所有文章除特别声明外，均采用 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-10-11
点向行列连边的网络流图优化成行列连边的二分图：CF1592F2
点向行列连边的网络流图优化成行列连边的二分图：CF1592F2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133764633 https://www.luogu.com.cn/problem/CF1592F2 做完F1，然后用1的结论来思考。 场上推了几个性质。首先op4的操作行列必然两两不同，所以op4最多 max(n,m)\max(n,m)max(n,m) 次。然后手玩发现只有除 (n,m)(n,m)(n,m) 的三个格子都为1，op4才有意义。 ...
2023-12-18
把状态拆成长链来跑网络流（转化为最小割）：LibreOJ - 2384
把状态拆成长链来跑网络流（转化为最小割）：LibreOJ - 2384 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135058691 https://vj.imken.moe/contest/598718#problem/C 一个点要确定一个取值，然后每个取值还有代价，我们就拆成一条链： 源汇点就可以连对应代价的差分 然后题目肯定有某些一堆限制，关于某两条链的取值有什么限制，我们就可以在链之间连很多很多无穷的边来解决，比如： 这就代表如果第一条链 ≥...
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-08-27
多次跑网络流（用于构造类）+霍尔定理证明可行：AGC317G
多次跑网络流（用于构造类）+霍尔定理证明可行：AGC317G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132517757 https://atcoder.jp/contests/abc317/tasks/abc317_g 一个很显然的思路，就是行向颜色连边，但约束条件展现出多个维度，所以可以考虑跑多次网络流。 但跑同样的网络流没有意义，所以每次跑完都要在残余网络上操作一下才可行。此题中，为了方便构造，就是对成功流了的边进行删除。 但多次跑网络流是否正确...
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，初始...