记录编号	240224	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]订货	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-03-22 12:46:31	内存使用	0.99 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 105;
const int inf = 1e8;
inline int get_num() {
	int ans = 0;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') tmp = getchar();
	while(tmp >= '0' && tmp <= '9') {
		ans = ans*10 + tmp-'0';
		tmp = getchar();
	}
	return ans;
} 
int n, m, v, s, t;
class cost_flow {
private:
	struct edge {
		int to, ne, le, v;
		edge() {}
		edge(int to_, int ne_, int le_, int v_) {
			to = to_, ne = ne_, le = le_, v = v_;
		}
	}e[maxn*maxn<<2];
	int head[maxn], tot;
	bool inque[maxn];
	int dis[maxn];
	int linkn[maxn];
	int linke[maxn];
public:
	inline void add_edge(int fr, int to, int cap, int v) {
		e[++tot] = edge(to, head[fr], cap, v); head[fr] = tot;
		e[++tot] = edge(fr, head[to], 0, -v); head[to] = tot;
	}
	inline bool spfa() {
		memset(dis, 127, sizeof(dis));
		queue<int> q;
		dis[s] = 0;
		inque[s] = true;
		q.push(s);
		while(!q.empty()) {
			int now = q.front(); q.pop();
			for(int i = head[now]; i; i = e[i].ne) {
				int to = e[i].to;
				if(e[i].le > 0 && dis[to] > dis[now]+e[i].v) {
					dis[to] = dis[now]+e[i].v;
					linke[to] = i;
					linkn[to] = now;
					if(!inque[to]) {
						inque[to] = true;
						q.push(to);
					} 
				}
			}
			inque[now] = false;
		}
		return dis[t] < inf;
	}
	inline int augment() {
		int now = t, min_flow = inf;
		while(now != s) {
			min_flow = min(min_flow, e[linke[now]].le);
			now = linkn[now];
		}
		now = t;
		while(now != s) {
			e[linke[now]].le -= min_flow;
			if(linke[now] & 1) e[linke[now]+1].le += min_flow;
			else e[linke[now]-1].le += min_flow;
			now = linkn[now];
		}
		return dis[t]*min_flow;
	}
	inline int solve() {
		int ans = 0;
		while(spfa())
			ans += augment();
		return ans;
	}
}smin; 
inline void read() {
	n = get_num();
	m = get_num();
	v = get_num();
	s = 2*n+1; t = s+1;
	int tmp;
	for(int i = 1; i <= n; i++) {
		tmp = get_num();
		smin.add_edge(i, t, tmp, 0);
	}
	for(int i = 1; i < n; i++) {
		tmp = get_num();
		smin.add_edge(s, i, inf, tmp); 
		smin.add_edge(i, i+1, v, m);
	}
	tmp = get_num();
	smin.add_edge(s, n, v, tmp); 
}
int main() {
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);
	read();
	printf("%d\n", smin.solve());
	return 0;
}