题解

思路推导

建立流网络：源点向城市 $i$ 连容量 $p_i$ 的边，城市 $i$ 向汇点连容量 $s_i$ 的边；对每个 $i<j$，从 $i$ 向 $j$ 连容量 $c$ 的边。该网络中的最大流恰好表示能够被销售的商品总量。

直接建图有平方条边，无法运行普通最大流。考虑最小割。设有一部分城市与源点位于割的同一侧，记为集合 $S$。割容量包含：

• 每个不在 $S$ 中的城市对应的 $p_i$；
• 每个在 $S$ 中的城市对应的 $s_i$；
• 每一对满足 $i<j$、$i\in S$、$j\notin S$ 的城市对应的 $c$。

因此只需在所有二进制城市划分中最小化上述代价。

做法

按编号从小到大处理城市。令 $dp_j$ 表示已经处理若干城市，其中恰有 $j$ 个城市被放入 $S$ 时的最小割容量。

处理城市 $i$ 时有两种选择：

• 把 $i$ 放入 $S$，新增割边为 $s_i$，转移到状态 $j+1$；
• 不把 $i$ 放入 $S$，新增源边 $p_i$，并且此前 $j$ 个属于 $S$ 的城市都向 $i$ 有容量 $c$ 的边，所以再增加 $cj$，状态仍为 $j$。

取全部状态最小值，即为最小割，也就是最大销售量。

正确性证明

流网络中，源点到城市的容量限制该城市可提供的商品量，城市到汇点的容量限制销售量，城市间边的方向和容量正好对应允许的运输。因此最大流等于最大销售量。

对任意割，城市集合 $S$ 完全决定割边：不在 $S$ 的城市切断源边，在 $S$ 的城市切断汇边，而从 $S$ 中较小编号城市指向补集城市的运输边也被切断。动态规划的两种转移分别精确加入当前城市属于补集或属于 $S$ 时新出现的全部割边，没有遗漏或重复。

所以动态规划枚举并正确计算了每一种割，最终最小值为最小割。由最大流最小割定理，所得结果就是最大销售量。

部分分算法

当 $n\le18$ 时，可以枚举所有 $2^n$ 个集合 $S$，在线性时间内计算每个割的容量。

当 $c=0$ 时，城市之间无法运输，各城市相互独立，答案为 $\sum_i\min(p_i,s_i)$。

复杂度分析

动态规划有 $n$ 轮，每轮至多 $n+1$ 个状态。时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。