CF1919F2 题解

· · 题解

题目

CF1919F2

分析

首先，题目可以转化为网络流。具体的，连三种边：

  1. 连 S\to i 的边，边权为 a_i（A 类边）。
  2. 连 i\to T 的边，边权为 b_i（B 类边）。
  3. 连 i\to i+1 的边，边权为 c_i（C 类边）。

但是，硬跑网络流肯定是不行的，考虑转化为最小割。可以分析这个图的性质。

性质：在最小割中，对于一个点 i，它的 A 类边和 B 类边恰好被割掉一条。

证明：

  • 如果都不割，则存在 S\to i\to T 的路径，不是割。
  • 如果都割掉，分两种情况讨论：
    1. 如果存在 S\to i 的路径，则不割掉 A 类边一定不劣。
    2. 如果不存在 S\to i 的路径，则不割掉 B 类边一定不劣。

于是可以用线段树维护贡献。每个节点中记录四个值，分别记录区间最左端和最右端割掉的是哪种边时的最小割。区间合并时，如果左区间的最右端割掉的是 B 类边，且右区间的最左端割掉的是 A 类边，则需要额外割掉连接它们的 C 类边。

代码

Code