题解【CF724E Goods transportation】

传送门。

$\texttt{Solution}$

有 $n$ 个城市，若 $i

第 $i$ 个城市初始有 $p_i$ 个货物，最多卖 $s_i$ 个货物。

求最多卖掉的货物的数量。

$1\le n\le 10^4$。

好神的题啊/se，但可能我理解太弱了，感觉楼下的 DP 讲的太模糊了

考虑一个非常显然的网络流：

这样建图的边数是 $n^2$ 级别的，跑网络流直接炸飞。

这时候就用到一个小 $\texttt{trick}$：最大流 $=$ 最小割。我们可以通过求最小割来求出最大流。

考虑 DP，设 $f_{i,j}$ 表示，到了第 $i$ 个点，有 $j$ 个和 $s$ 的边未被割掉。

为什么这个东西可以 DP 呢？因为题目中有一个重要条件：$i

回到正题，考虑转移。

一个点 $i$ 有两种选择，断掉它于 $s$ 的边，或断掉与 $t$ 的边。

若断掉与 $s$ 的边，不光需要断掉与 $s$ 之间，容量为 $p_i$ 的边，还需要断掉，和 $s$ 之间没有断掉边的，那 $j$ 个点之间的边，每一条边的容量都是 $c$，一共需要断 $j$ 条，所以需要断掉的容量是 $c\times j$。

这只是 $i$ 一个点的花费，它还需要加上前 $i-1$ 个点的花费。

此时 $i$ 是不算在 $j$ 个节点内的，所以前 $i-1$ 个节点中，一共有 $j$ 个是与 $s$ 直接相连。

所以此时，$f_{i,j}=f_{i-1,j}+p_i+c\times j$。

同理，如果断掉与 $t$ 的边，则只需要断掉 $s_i$ 那条边，但是此时，$i$ 已经算在 $j$ 个点内了，所以前 $i-1$ 个只有 $j-1$ 个与 $s$ 直接相连。

所以此时，$f_{i,j}=f_{i-1,j-1}+s_i$。

两者取 $\min$，得到转移方程：

$$f_{i,j}=\min(f_{i-1,j}+p_i+c\times j,f_{i-1,j-1}+s_i)$$

最终答案为 $\min_{0\le i\le n}\{f_{n,i}\}$。

但是空间会爆炸，所以直接将第一维滚动数组滚掉就好了。

最终时间复杂度 $\Theta(n^2)$，空间复杂度 $\Theta(n)$，可以通过本题。

代码就不放了，核心也就 $\texttt{5,6}$ 行的样子，需要者私信。

$\texttt{AC}$ 链接。

$$\texttt{The End.by UF}$$

动态规划 DP 网络流最小割