HMF-have much fun Site
文章
标签
16
联系方式戳我~
阅
【题解】CF280D k-Maximum Subsequence Sum
热度: loading...
模拟费用流的入门好题。
所谓 模拟费用流 ，就是在问题可以用费用流的思想解决，但却不适用费用流的复杂度的时候，我们用一些方法（大部分时候是数据结构）来模拟费用流进行的过程，从而降低复杂度，通过题目的算法。
考虑先对题目构建费用流模型，将点的权值转换到边上，即构造 个点，点 和点 之间的边的权值为 ，从源点向每个点连边，从每个点向汇点连边，从 点流到 点说明取了 这一段的值，求最大费用流。
考虑直接模拟费用流的过程，最大费用流每次选择费用最大的一条路径增广，由于我们连边的限制，最大路径一定是序列里的一个区间。由于是一个区间，我们可以使用线段树直接维护最大的区间，直接加上这个区间的贡献，然后再按照费用流的步骤将区间内的费用取反。
每一次流动如果流的位置没取过则相当于取了这一段区间，如果取过了则相当于将这一段区间消除（即反悔）。每次流之后实质上取到的区间一定会增加一个，否则相当于它将一次取得区间完全消除，而增广的每一次都是有意义的，不可能被完全消除贡献。
因此我们用线段树每次取最大区间，取完后取反，这个过程进行 次，取到的最大权值就是答案。
费用流的本质就是可以反悔的贪心，模拟费用流也继承了这一点。
其他例题：
赏
