记录编号	38110	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	1.428 s
提交时间	2012-04-13 09:54:55	内存使用	10.28 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 200 * 4 + 10, INF = ~0u>>2;
int n, pp, s, t, fw, fc, sw, sc;
int G[N][N], w[N][N], c[N][N], f[N][N];
int r[N], p[N], d[N], l[N], a, g, e;
inline void adde(int u, int v, int W, int C) {
    w[u][v] = W;
    c[u][v] = C;
    w[v][u] = 0;
    c[v][u] = -C;
}
void MinCostFlow() {
    queue<int> q;
    for(; ; ) {
        for(int i=s; i<=t; i++)
            d[i] = INF, l[i] = 0;
        d[s] = 0;
        q.push(s);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            l[u] = 0;
            for(int v=s; v<=t; v++)
                if(w[u][v] > f[u][v] && d[v] > d[u] + c[u][v]) {
                    d[v] = d[u] + c[u][v];
                    p[v] = u;
                    if(!l[v]) {
                        l[v] = 1;
                        q.push(v);
                    }
                }
        }
        if(d[t] == INF) break;
        a = INF;
        for(int u=t; u!=s; u=p[u])
            a = min(a, w[p[u]][u] - f[p[u]][u]);
        for(int u=t; u!=s; u=p[u]) {
            f[p[u]][u] += a;
            f[u][p[u]] -= a;
        }
        g += d[t] * a;
        e += a;
    }
}
int main() {
    freopen("napkin.in", "r", stdin);
    freopen("napkin.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", r+i);
    scanf("%d %d %d %d %d", &pp, &fw, &fc, &sw, &sc);
    s = 0; t = n*2 + 1;
    for(int i=1; i<=n; i++) {
        adde(s, i, r[i], 0);
        adde(i+n, t, r[i], 0);
        adde(s, i+n, INF, pp);
        if(i < n) adde(i, i+1, INF, 0);
        if(i+fw <= n) adde(i, i+fw+n, INF, fc);
        if(i+sw <= n) adde(i, i+sw+n, INF, sc);
    }
    MinCostFlow();
    printf("%d\n", g);
    return 0;
}