可能的模拟网络流部分思路整理（CF1408H）
可能的模拟网络流部分思路整理（CF1408H）
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093428
https://www.luogu.com.cn/problem/CF1408H
先转换
模拟网络流，所以要么割最上面一层，要么割最下面一层。
对于最上一层，肯定是左边连续+右边连续。
考虑枚举左边连续，对应到某些颜色节点，又对应到某些右边节点。
对右边节点建棵线段树，由于左边的点已经确定，先假设下面的和右边的点全部割掉。
右边的点全部割掉，所以线段树初始全为-1。
颜色节点对应到右边节点位置时，在那个位置+1，表示可以少割一条颜色边。
然后线段树求最大后缀和即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-03
对于模拟最大流的一些猜测
对于模拟最大流的一些猜测 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093553 先把最大流转成最小割。 然后对最小割分类讨论，观察性质，看看有什么不用跑最大流的做法？ 等我长大再回来想。
2023-08-03
网络最大流
网络最大流 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132091032 < Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流 - 洛谷 > 先bfs分层 2.dfs增广，当前弧优化 重复以上步骤 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...
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/132091530 新建两个超级源、汇点。 原先是a->b，范围[c,d]。现在变成 S->b，c a->T，c a->b，d-c ZOJ2314ReactorCooling_网络流-个人编程笔记
2023-08-04
分类讨论+反悔贪心来实现模拟费用流：[NOI2019] 序列
分类讨论+反悔贪心来实现模拟费用流：[NOI2019] 序列 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132112120 https://www.luogu.com.cn/problem/P5470 很容易把费用流建出来。 然后要模拟这个过程，把核心要点，也就是 K−LK-LK−L 这个限制提取出来。 因为在此限制下答案不劣，所以优先枚举这个限制下的答案。 模拟费用流，所以必然有反悔贪心，分类讨论一下。 总结下来，对于模拟费用流的方法： 分类讨论...
2023-08-10
点分治小结
点分治小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217048 https://www.luogu.com.cn/problem/P3806 dfs1：找到当前重心 dfs2：统计当前每个点到重心的距离 dfz：点分治 找重心，处理出 xxx 所有儿子子树和非 xxx 子树的大小最大值，这个最大值最小的点 xxx 就是答案 注意这个过程中统计非 xxx 子树大小需要统计当前分治区间的大小 sumsumsum ，要时刻注意维护这个...