可以在 cnblog 中阅读。
题意
有 \(n\) 座城市，第 \(i\) 座城市生产了 \(p_i\) 件货物，最多可以出售 \(s_i\) 件货物，编号小的城市可以向编号大的城市运输至多 \(c\) 件货物，问最多能出售多少货物。
\(n \le 10^4\)。
分析
乍一看是一个网络流问题，可以这样建图，令 \(S\) 为源点 \(T\) 为汇点：
\[S \xrightarrow{p_i} i \xrightarrow{s_i} T
\]
\[i \xrightarrow{c} j (i < j)
\]
然后跑一个最大流就可以。但这样建边第二类就会有 \(O(n^2)\) 条边，寄。
模拟费用流就是应对这样的情况的。我们把最大流问题转换为最小割问题，然后考虑使用 DP 求解。
令 \(f(i,j)\) 表示前 \(i\) 个点，\(j\) 个点与 \(S\) 的连边未断开，注意到 \((S,i)\) 与 \((i,T)\) 必断其一，则有转移：
\[f(i,j) = \min
\begin{cases}f(i-1,j) + p_i + c \times j \\f(i-1,j-1) + s_i
\end{cases}\]
分别表示：
- 断开 \((S,i)\) 需要断开与前面所有未断开与 \(S\) 连边的点的连边；
- 断开 \((i,T)\)。
时间复杂度 \(O(n^2)\)。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)const int N=1e5+5;
int n,c;
int s[N],p[N];
int f[N];signed main()
{IOS;cin>>n>>c;for(int i=1;i<=n;i++) cin>>p[i];for(int i=1;i<=n;i++) cin>>s[i];for(int i=1;i<=n;i++){f[i]=f[i-1]+s[i];for(int j=i-1;j>=1;j--)f[j]=min(f[j]+c*j+p[i],f[j-1]+s[i]);f[0]+=p[i];}int ans=1e16;for(int i=0;i<=n;i++) ans=min(ans,f[i]);cout<<ans<<endl;return 0;
}
