记录编号	208082	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2015-11-15 13:46:31	内存使用	0.36 MiB

#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
const int V(411), E(3011), inf(0x3f3f3f3f);
int v[V], tv, h[V], n[E], e[E], c[E], w[E], et(-1), d[V], le[V], lp[V], s, t, ans, need[205];
inline void ins(int f, int t, int cap, int cost){
	n[++et] = h[f]; h[f] = et; e[et] = t; c[et] = cap; w[et] = cost;
	n[++et] = h[t]; h[t] = et; e[et] = f; c[et] = 0; w[et] = -cost;
}
bool spfa(){
	int i, j;
	deque<int> q;
	++tv;
	memset(d, inf, sizeof(d));
	d[s] = 0;
	q.push_back(s);
	while (!q.empty()){
		j = q.front(); q.pop_front(); v[j] = 0;
		for (i = h[j]; i != -1; i = n[i])
			if (c[i] && d[e[i]] > d[j] + w[i]){
				d[e[i]] = d[j] + w[i];
				if (v[e[i]] != tv)
					if (!q.empty() && d[e[i]] <= d[q.front()]) q.push_front(e[i]), v[e[i]] = tv;
					else q.push_back(e[i]), v[e[i]] = tv;
			}
	}
	return d[t] != inf;
}
int dfs(int p, int r){
	if (p == t) return r;
	int i, j, f(0);
	v[p] = tv;
	for (i = h[p]; i != -1 && r; i = n[i])
		if (v[e[i]] != tv && c[i] && d[e[i]] == d[p] + w[i]){
			j = dfs(e[i], r < c[i]? r: c[i]);
			f += j; r -= j;
			c[i] -= j; c[i ^ 1] += j;
			ans += j * w[i];
		}
	v[p] = 0;
	if (!f) d[p] = -inf;
	return f;
}
inline void dinic(){
	while (spfa())
		do ++tv; while (dfs(s, inf));
}
int main(){
	freopen("napkin.in", "r", stdin);
	freopen("napkin.out", "w", stdout);
	memset(h, -1, sizeof(h));
	int tt, nc, ft, fc, st, sc, i, j;
	for (scanf("%d", &tt), i = 1; i <= tt; scanf("%d", &need[i++]));
	scanf("%d%d%d%d%d", &nc, &ft, &fc, &st, &sc);
	t = tt * 2 + 1;
	for (i = 1; i <= tt; ++i){
		j = need[i];
		ins(s, i, j, 0);
		ins(s, i + tt, inf, nc);
		if (i < tt) ins(i, i + 1, inf, 0);
		if (i + ft <= tt) ins(i, i + ft + tt, inf, fc);
		if (i + st <= tt) ins(i, i + st + tt, inf, sc);
		ins(i + tt, t, j, 0);
	}
	dinic();
	printf("%d\n", ans);
	return 0;
}