简要题意
一家公司销售一种商品，在时刻 \(i\) 可以需要 \(U_i\) 份商品。第 \(i\) 时刻向生产方购买 \(1\) 份商品需要 \(d_i\) 的代价。\(i-1\) 时刻的 \(1\) 份商品滞留到 \(i\) 时刻，需要花费 \(m\) 的代价，且一共只能滞留 \(S\) 份商品。
问经营 \(n\) 个时刻的最小花费。
\(0\leq n\leq 50, 0\leq m \leq 10, 0\leq S\leq 10000,0 \leq U_i \leq 10000,0 \leq d_i \leq 100\)
思路
这道题和 P1251 餐巾计划问题 差不多，都是费用流建模题。
对于 \(i\) 时刻，建立点 \(i\)，然后考虑连边：
- 对于滞留商品，我们连边 \((i-1,i,S,m)\)（这一点显然易见）。
- 对于需要商品，我们像餐厅计划问题一样，建立超级汇点 \(T\)，然后连边 \((i,T,U_i,0)\)。
- 对于购买商品，我们像餐厅计划问题一样，建立超级源点 \(S\)，然后连边 \((S,i,+\infty,d_i)\)。
这里再解释一下连边：需要商品时，不能从上一个节点连边，因为剩余不方便计算。但是我们如果连向汇点，那么就直接限制了流量，也就是说，如果要有流量，那么必须要有 \(U_i\) 的流量。购买商品时，没有商品份数限制，因此流量为 \(+\infty\)，买一份需要 \(d_i\)，所以费用时 \(d_i\)。总之，这里流量时商品个数，费用时花费。
然后直接跑 \(S\) 为源 \(T\) 为汇的最小费用最大流即可。时间复杂度 \(O(\operatorname{mcmf}(n,n))\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s;
namespace MCMF{
struct edge{
int nxt,to,cap,cost;
} g[100005];
int head[100005],ec=-1;
void add(int from,int to,int cap,int cost){
g[++ec].nxt=head[from];
g[ec].to=to;
g[ec].cap=cap;
g[ec].cost=cost;
head[from]=ec;
}
void add_edge(int from,int to,int cap,int cost){
add(from,to,cap,cost);
add(to,from,0,-cost);
}
queue<int> q;
bool vis[100005];
int flow[100005];
int dis[100005];
int pre[100005];
int last[100005];
bool spfa(int s,int t){
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
q.push(s);
vis[s]=1;
dis[s]=0;
pre[t]=-1;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=g[i].nxt){
int v=g[i].to;
if(g[i].cap>0 && dis[v]>dis[u]+g[i].cost){
dis[v]=dis[u]+g[i].cost;
pre[v]=u;
last[v]=i;
flow[v]=min(flow[u],g[i].cap);
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
return pre[t]!=-1;
}
pair<int,int> MCMF(int s,int t){
int maxflow=0,mincost=0;
while(spfa(s,t)){
int now=t;
maxflow+=flow[t];
mincost+=flow[t]*dis[t];
while(now!=s){
g[last[now]].cap-=flow[t];
g[last[now]^1].cap+=flow[t];
now=pre[now];
}
}
return make_pair(maxflow,mincost);
}
}
int S,T;
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
memset(MCMF::head,-1,sizeof(MCMF::head));
MCMF::ec=-1;
cin>>n>>m>>s;
S=0,T=n+1;
for(int i=1,u;i<=n;i++){
cin>>u;
MCMF::add_edge(i,T,u,0);
}
for(int i=1,d;i<=n;i++){
cin>>d;
MCMF::add_edge(S,i,LLONG_MAX,d);
}
for(int i=2;i<=n;i++){
MCMF::add_edge(i-1,i,s,m);
}
cout<<MCMF::MCMF(S,T).second<<'\n';
return 0;
}