标准的费用流问题，关键在于巧妙地建模
一共有n个月份，源点设为0，汇点设为n+1
1.源点向所有月份连边，容量为正无穷，费用为该月进货的费用
2.每个月向下一个月连边，容量为仓库容量，费用为存货费用
3.每个月向汇点连边，容量为该月卖货的数量，费用为0（卖货不会产生费用）
用最小费用最大流求解即可
————————————————
版权声明：本文为CSDN博主「ynhnxn」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/C_sat/article/details/123443008
1 #include<bits/stdc++.h>
2 using namespace std;
3 int INF=20000000,tot=1,n,ans=0;
4 int nex[1000],adj[1000],to[1000],cap[1000],cost[1000];
5 int d[60],que[2000000];
6 bool vis[1000];
7
8 void add(int u,int v,int w,int c){
9 nex[++tot]=adj[u];
10 adj[u]=tot;
11 to[tot]=v;
12 cap[tot]=w;
13 cost[tot]=c;
14 }
15
16 int SPFA(){//标准SPFA
17 int q1=0,q2=1;
18 que[1]=0;
19 for(int i=1;i<=n+1;i++) d[i]=INF,vis[i]=0;
20 while(q1<q2){
21 int x=que[++q1];
22 vis[x]=0;
23 for(int k=adj[x];k;k=nex[k]){
24 int y=to[k];
25 if(d[x]+cost[k]<d[y]&&cap[k]){
26 d[y]=d[x]+cost[k];
27 if(!vis[y]){
28 vis[y]=1;que[++q2]=y;
29 }
30 }
31 }
32 }
33 if(d[n+1]==INF) return 0;
34 for(int i=0;i<=n+1;i++){
35 if(d[i]!=INF) vis[i]=0;
36 }
37 return 1;
38 }
39
40 int dinic(int u,int fw){//标准dinic
41 if(u==n+1){
42 ans+=fw*d[n+1];
43 return fw;
44 }
45 vis[u]=1;
46 int rest=fw;
47 for(int i=adj[u];i&&rest;i=nex[i]){
48 int v=to[i];
49 if(!vis[v]&&d[v]==d[u]+cost[i]&&cap[i]>0){
50 int k=dinic(v,min(rest,cap[i]));
51 if(k){
52 rest-=k;
53 cap[i]-=k;
54 cap[i^1]+=k;
55 }
56 }
57 }
58 return fw-rest;
59 }
60
61 int main(){//源点为0，汇点为n+1
62 int x,m,s;
63 scanf("%d%d%d",&n,&m,&s);//月份数，存贮费，仓库容量
64 for(int i=1;i<=n;i++){
65 scanf("%d",&x);//需求量
66 add(i,n+1,x,0);
67 add(n+1,i,0,0);//每个月向汇点连边，容量为x，费用为0
68 if(i!=n) add(i,i+1,s,m),add(i+1,i,0,-m);//向下一个月连边，容量就是仓库容量s，费用是m
69 }
70 for(int i=1;i<=n;i++){
71 scanf("%d",&x);//订货单价
72 add(0,i,INF,x);
73 add(i,0,0,-x);//源点向每个月连边，容量为正无穷，费用为订货价格
74 }
75 while(SPFA()) dinic(0,INF);//最小费用最大流
76 cout<<ans;
77 }
