记录编号	305770	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]订货	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-09-11 10:45:57	内存使用	0.29 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N=51,M=410,INF=1000000000;
int cnt=1,fir[N],nxt[M],to[M],cap[M],val[M];
int dis[N],vis[N],path[N];queue<int>q;
int n,m,S;

void addedge(int a,int b,int c,int v){
	nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;
	cap[cnt]=c;val[cnt]=v;
}

int BFS(int s,int t){
	for(int i=1;i<=t;i++)dis[i]=INF;
	dis[s]=0;q.push(s);vis[s]=1;
	while(!q.empty()){
		int x=q.front();q.pop();vis[x]=0;
		for(int i=fir[x];i;i=nxt[i])
			if(cap[i]&&dis[to[i]]>dis[x]+val[i]){
				dis[to[i]]=dis[x]+val[i];path[to[i]]=i;
				if(!vis[to[i]])q.push(to[i]);vis[to[i]]=1;
			}
	}
	return dis[t];
}

int Aug(int s,int t){
	int p=t,f=INF;
	while(p!=s){
		f=min(f,cap[path[p]]);
		p=to[path[p]^1];
	}p=t;
	while(p!=s){
		cap[path[p]]-=f;
		cap[path[p]^1]+=f;
		p=to[path[p]^1];	
	}
	return f;
}

int McMf(int s,int t){
	int ret=0,d;
	while((d=BFS(s,t))!=INF)
		ret+=d*Aug(s,t);
	return ret;
}
int s,t;
int main(){
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>S;s=0;t=n+1;
	for(int i=1,u;i<=n;i++){
		cin>>u;
		addedge(i,t,u,0);
		addedge(t,i,0,0);
	}
	for(int i=1,w;i<=n;i++){
		cin>>w;
		addedge(s,i,INF,w);
		addedge(i,s,0,-w);
	}
	for(int i=1;i<n;i++){
		addedge(i,i+1,S,m);
		addedge(i+1,i,0,-m);
	}
	cout<<McMf(s,t)<<"\n";
}