- 1#include 2#include 3#include 4#include 5#define N 4010 6#define M 100005 7#define INF~ (1 << 31) 8#define min(x, y)((x) < (y) ? (x) : (y)) 9 10 int a,
- p,
- m,
- f,
- n,
- g,
- s,
- t,
- cnt;
- 11 int head[N],
- to[M],
- val[M],
- cost[M],
- next[M],
- dis[N],
- pre[N];
- 12 bool vis[N];
- 13 long long sum;
- 14 15 inline int read() 16 {
- 17 int x = 0,
- f = 1;
- 18 char ch = getchar();
- 19
- for (; ! isdigit(ch); ch = getchar()) if (ch == ' - ') f = -1;
- 20
- for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
- 21
- return x * f;
- 22
- }
- 23 24 inline void add(int x, int y, int z, int c) 25 {
- 26 to[cnt] = y;
- 27 val[cnt] = z;
- 28 cost[cnt] = c;
- 29 next[cnt] = head[x];
- 30 head[x] = cnt++;
- 31
- }
- 32 33 inline bool spfa() 34 {
- 35 int i,
- u,
- v;
- 36 std: :queue < int > q;
- 37 memset(vis, 0, sizeof(vis));
- 38 memset(pre, -1, sizeof(pre));
- 39 memset(dis, 127 / 3, sizeof(dis));
- 40 q.push(s);
- 41 dis[s] = 0;
- 42
- while (!q.empty()) 43 {
- 44 u = q.front(),
- q.pop();
- 45 vis[u] = 0;
- 46
- for (i = head[u]; i ^ -1; i = next[i]) 47 {
- 48 v = to[i];
- 49
- if (val[i] && dis[v] > dis[u] + cost[i]) 50 {
- 51 dis[v] = dis[u] + cost[i];
- 52 pre[v] = i;
- 53
- if (!vis[v]) 54 {
- 55 q.push(v);
- 56 vis[v] = 1;
- 57
- }
- 58
- }
- 59
- }
- 60
- }
- 61
- return pre[t] ^ -1;
- 62
- }
- 63 64 int main() 65 {
- 66 int i,
- x,
- d;
- 67 a = read();
- 68 s = 0,
- t = (a << 1) + 1;
- 69 memset(head, -1, sizeof(head));
- 70
- for (i = 1; i <= a; i++) 71 {
- 72 x = read();
- 73 add(s, i, x, 0),
- add(i, s, 0, 0);
- 74 add(i + a, t, x, 0),
- add(t, i + a, 0, 0);
- 75
- }
- 76 p = read();
- 77 m = read();
- 78 f = read();
- 79 n = read();
- 80 g = read();
- 81
- for (i = a + 1; i <= a + a; i++) add(s, i, INF, p),
- add(i, s, 0, -p);
- 82
- for (i = 1; i < a; i++) add(i, i + 1, INF, 0),
- add(i + 1, i, 0, 0);
- 83
- for (i = 1; i <= a - m; i++) add(i, i + a + m, INF, f),
- add(i + a + m, i, 0, -f);
- 84
- for (i = 1; i <= a - n; i++) add(i, i + a + n, INF, g),
- add(i + a + n, i, 0, -g);
- 85
- while (spfa()) 86 {
- 87 d = 1e9;
- 88
- for (i = pre[t]; i ^ -1; i = pre[to[i ^ 1]]) d = min(d, val[i]);
- 89
- for (i = pre[t]; i ^ -1; i = pre[to[i ^ 1]]) 90 {
- 91 val[i] -= d;
- 92 val[i ^ 1] += d;
- 93
- }
- 94 sum += (long long) dis[t] * d;
- 95
- }
- 96 printf("%lldn", sum);
- 97
- return 0;
- 98
- }
来源: http://www.bubuko.com/infodetail-2102548.html