https://www.luogu.com.cn/problem/AT_arc107_f
理论上界为 ∑ ∣ b i ∣ \sum |b_i| ∑∣bi∣。考虑现在减少会有什么情况:
- 不选。代价为 a i + ∣ b i ∣ a_i+|b_i| ai+∣bi∣
- 原先为正,所在连通块取绝对值后变负。代价为 − 2 ∣ b i ∣ -2|b_i| −2∣bi∣
- 原先为负,所在连通块取绝对值后变正。代价为 − 2 ∣ b i ∣ -2|b_i| −2∣bi∣
有一堆代价,很容易想到流 / 割。
然后每个联通块有两种取值(正 / 负),正好对应源汇点,因为是归类,所以是割。
至于第一种情况,因为只和自已有关,显然拆点连边。
现在还有一个问题,同一个联通块必须同号。转化一下是什么,有边相连的点必须归类到同源同汇(也就是归类到同一边)。经典套路,连一条反向无穷大的边即可。