分类讨论+反悔贪心来实现模拟费用流：[NOI2019] 序列
分类讨论+反悔贪心来实现模拟费用流：[NOI2019] 序列
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132112120
https://www.luogu.com.cn/problem/P5470
很容易把费用流建出来。
然后要模拟这个过程，把核心要点，也就是 这个限制提取出来。
因为在此限制下答案不劣，所以优先枚举这个限制下的答案。
模拟费用流，所以必然有反悔贪心，分类讨论一下。
总结下来，对于模拟费用流的方法：
-
分类讨论从 的增广路
-
网络流的反边 反悔贪心
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-11-06
上下界网络流小结
上下界网络流小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093889 正式请看：https://oi-wiki.org/graph/flow/bound/ 无源汇上下界可行流 新建源汇 S,TS,TS,T ，若 a→ba\to ba→b 有 [c,d][c,d][c,d] 。网络流中上界肯定满足。 我们变成： S→b,cS\to b,cS→b,c a→T,ca\to T,ca→T,c a→b,c−da\to b,c-da→b,c−...
2023-08-03
对于模拟最大流的一些猜测
对于模拟最大流的一些猜测 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093553 先把最大流转成最小割。 然后对最小割分类讨论，观察性质，看看有什么不用跑最大流的做法？ 等我长大再回来想。
2023-08-03
无源汇上下界可行流
无源汇上下界可行流 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132091530 新建两个超级源、汇点。 原先是a->b，范围[c,d]。现在变成 S->b，c a->T，c a->b，d-c ZOJ2314ReactorCooling_网络流-个人编程笔记
2023-09-16
可能的模拟网络流部分思路整理（CF1408H）
可能的模拟网络流部分思路整理（CF1408H） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093428 https://www.luogu.com.cn/problem/CF1408H 先转换 模拟网络流，所以要么割最上面一层，要么割最下面一层。 对于最上一层，肯定是左边连续+右边连续。 考虑枚举左边连续，对应到某些颜色节点，又对应到某些右边节点。 对右边节点建棵线段树，由于左边的点已经确定，先假设下面的和右边的点全部割掉。 右边的点全部割掉，所以...
2023-08-03
网络最大流
网络最大流 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132091032 < Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流 - 洛谷 > 先bfs分层 2.dfs增广，当前弧优化 重复以上步骤 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...
2022-01-24
【P5994 [PA2014]Kuglarz】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15838986.html 题目链接 题目 魔术师的桌子上有 nnn 个杯子排成一行，编号为 1,2,…,n1,2,…,n1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。 花费 cijc_{ij}cij 元，魔术师就会告诉你杯子 i,i+1,…,ji,i+1,…,ji,i+1,…,j 底下藏有球的总数的奇偶性。 采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？ 思路 前缀和建图...