裸的费用流了= =从源点向每个点连费用为di,从汇点向每个点连流量为ui,每个点向下一个点连费用为m,流量为s的边就行了
CODE:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 65
#define maxm 400
#define inf 0x7fffffff
struct edges{
int to,next,cap,dist;
}edge[maxm];
int next[maxn],l;
int s,t;
int addedge(int x,int y,int z,int cap){
l++;
edge[l*2]=(edges){y,next[x],cap,z};
edge[l*2+1]=(edges){x,next[y],0,-z};
next[x]=l*2;next[y]=l*2+1;
return 0;
}
int dist[maxn],way[maxn];
bool b[maxn];
queue<int> q;
bool spfa(){
for (int i=1;i<=t;i++) dist[i]=inf;
dist[s]=0;
q.push(s);
while (!q.empty()){
int u=q.front();q.pop();
b[u]=0;
for (int i=next[u];i;i=edge[i].next)
if (edge[i].cap&&dist[edge[i].to]>dist[u]+edge[i].dist){
dist[edge[i].to]=dist[u]+edge[i].dist;
way[edge[i].to]=i;
if(!b[edge[i].to]){
b[edge[i].to]=1;
q.push(edge[i].to);
}
}
}
if (dist[t]==inf) return 0;
return 1;
}
int mcmf(){
int cost=0;
while (spfa()){
int flow=inf,x=t;
while (x!=s){
flow=min(flow,edge[way[x]].cap);
x=edge[way[x]^1].to;
}
cost+=dist[t]*flow;
x=t;
while (x!=s){
edge[way[x]].cap-=flow;
edge[way[x]^1].cap+=flow;
x=edge[way[x]^1].to;
}
}
return cost;
}
int main(){
int n,m,S;
scanf("%d%d%d",&n,&m,&S);
s=n+1;t=n+2;
for (int i=1;i<n;i++) addedge(i,i+1,m,S);
for (int i=1;i<=n;i++) {
int x;
scanf("%d",&x);
addedge(i,t,0,x);
}
for (int i=1;i<=n;i++) {
int x;
scanf("%d",&x);
addedge(s,i,x,inf);
}
printf("%d",mcmf());
return 0;
}