- 1#include 2#include 3#include 4#include 5#include 6 using namespace std;
- 7 const int N = 2005,
- INF = 1999999999;
- 8 int gi() {
- 9 int str = 0;
- char ch = getchar();
- 10
- while (ch > '9' || ch < '0') ch = getchar();
- 11
- while (ch >= '0' && ch <= '9') str = str * 10 + ch - '0',
- ch = getchar();
- 12
- return str;
- 13
- }
- 14 int n,
- s,
- sn,
- p,
- F,
- fn,
- T,
- S = 0,
- ans = 0;
- 15 int num = 1,
- head[N],
- f[N],
- vis[N],
- q[N * 10],
- pre[N];
- 16 struct Lin {
- 17 int next,
- to,
- dis,
- cost;
- 18
- }
- a[1000001];
- 19 void init(int x, int y, int z, int cost) {
- 20 a[++num].next = head[x];
- 21 a[num].to = y;
- 22 a[num].dis = z;
- 23 a[num].cost = cost;
- 24 head[x] = num;
- 25 a[++num].next = head[y];
- 26 a[num].to = x;
- 27 a[num].dis = 0;
- 28 a[num].cost = -cost;
- 29 head[y] = num;
- 30
- }
- 31 void Change() 32 {
- 33 int x = T,
- flow = INF;
- 34
- while (x) {
- 35 flow = min(flow, a[pre[x]].dis);
- 36 x = a[pre[x] ^ 1].to;
- 37
- }
- 38 x = T;
- 39
- while (x) {
- 40 a[pre[x]].dis -= flow;
- 41 a[pre[x] ^ 1].dis += flow;
- 42 ans += a[pre[x]].cost * flow;
- 43 x = a[pre[x] ^ 1].to;
- 44
- }
- 45
- }
- 46 bool spfa() 47 {
- 48
- for (int i = 0; i <= T; i++) f[i] = INF,
- vis[i] = false;
- 49 int t = 0,
- sum = 1,
- x,
- u;
- 50 q[1] = S;
- f[S] = 0;
- vis[S] = true;
- 51
- while (t != sum) 52 {
- 53 x = q[++t];
- 54
- for (int i = head[x]; i; i = a[i].next) 55 {
- 56
- if (a[i].dis <= 0) continue;
- 57 u = a[i].to;
- 58
- if (f[x] + a[i].cost < f[u]) 59 {
- 60 f[u] = f[x] + a[i].cost;
- 61 pre[u] = i;
- 62
- if (!vis[u]) vis[u] = true,
- q[++sum] = u;
- 63
- }
- 64
- }
- 65 vis[x] = false;
- 66
- }
- 67
- return f[T] != INF;
- 68
- }
- 69 int main() 70 {
- 71 //freopen("pp.in","r",stdin);
- 72 int x;
- 73 n = gi();
- p = gi();
- fn = gi();
- F = gi();
- sn = gi();
- s = gi();
- T = (n << 1) + 1;
- 74
- for (int i = 1; i <= n; i++) {
- 75 x = gi();
- 76 init(S, i, x, 0);
- 77 init(i + n, T, x, 0);
- 78 init(S, i + n, x, p);
- 79
- if (i1, INF, 0);
- 80
- if (i + fn <= n) init(i, i + n + fn, INF, F);
- 81
- if (i + sn <= n) init(i, i + n + sn, INF, s);
- 82
- }
- 83
- while (spfa()) Change();
- 84 printf("%d", ans);
- 85
- return 0;
- 86
- }
来源: http://www.bubuko.com/infodetail-2080061.html