到这题为止网络流 24 题也快刷完了呢,还剩下几道码量特大的等着以后有空去浪费时间(逃

这题一眼最小费用最大流,一开始我想了个类似于 NOI2008 志愿者招募 之类的利用满流的方法,但是一直没有调出来。后来怂了,直接连边,最后因为有个 - 1 没有删干净还是调了老半天。orz ,我还是太菜了。

把每一天分成两个节点,一个接受干净的毛巾,一个输出用过的毛巾。直接在这两个点之间连边显然不现实,我们可以分别把这两个点和源点、汇点连边。然后再按照题目条件一一连上对应边。这样最大流肯定能够跑满,求最小费用的话就是这图的最小费用最大流了。

这告诉我们对于不清楚的知识点不要瞎用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
#define rep(i,l,r) for (int i = l; i <= r; i++)
#define getc(x) getchar(x)
#define putc(x) putchar(x)

template <typename T> inline void read(T &x) {
x = 0; register char ch; register bool fl = 0;
while (ch = getc(), ch < 48 || 57 < ch) fl ^= ch == '-'; x = (ch & 15);
while (ch = getc(), 47 < ch && ch < 58) x = (x << 1) + (x << 3) + (ch & 15);
if (fl) x = -x;
}
template <typename T> inline void print(T x, char c = '\n') {
static int buf[40];
if (x == 0) { putc('0'); return; }
if (x < 0) putc('-'), x = -x;
for (buf[0] = 0; x; x /= 10) buf[++buf[0]] = x % 10 + 48;
while (buf[0]) putc((char) buf[buf[0]--]);
putc(c);
}

const int maxn = 4010, maxe = 50010;
const int inf = 1000000000;

int n, m, u, v, l, r, s, e, p;
int t1, t2, v1, v2, tmp, flow;
int a[maxn], pre[maxn], q[maxn], inq[maxn];
ll ans, dis[maxn];

int tot = 2, hed[maxn], nxt[maxe], to[maxe], val[maxe], cst[maxe];

inline void add_simple_edge(int u, int v, int w, int c) {
nxt[tot] = hed[u], to[tot] = v;
val[tot] = w, cst[tot] = c;
hed[u] = tot++;
}

inline void add_edge(int u, int v, int w, int c) {
add_simple_edge(u, v, w, c);
add_simple_edge(v, u, 0, -c);
}

bool spfa() {
memset(dis, 127, sizeof(dis));
memset(pre, 0, sizeof(pre));
l = r = 1, q[1] = s, dis[s] = 0, inq[s] = 1;
while (l <= r) {
u = q[(l++) % (e + 10)], inq[u] = 0;
for (int i = hed[u], v = to[i]; i; i = nxt[i], v = to[i])
if (val[i] && dis[v] > dis[u] + cst[i]) {
dis[v] = dis[u] + cst[i];
pre[v] = i;
if (!inq[v]) {
inq[v] = 1;
q[(++r) % (e + 10)] = v;
}
}
}
return pre[e];
}

int main() {

read(n), s = (n << 1) + 1, e = s + 1;
for (int i = 1; i <= n; i++)
read(a[i]);
read(p), read(t1), read(v1), read(t2), read(v2);

for (int i = 1; i <= n; i++)
add_edge(s, i + n, a[i], 0);
for (int i = 1; i <= n; i++)
add_edge(i, e, a[i], 0);
for (int i = 1; i <= n; i++)
add_edge(s, i, inf, p);
for (int i = 1; i + t1 <= n; i++)
add_edge(i + n, i + t1, inf, v1);
for (int i = 1; i + t2 <= n; i++)
add_edge(i + n, i + t2, inf, v2);
for (int i = 1; i < n; i++)
add_edge(i, i + 1, inf, 0);

while (spfa()) {
flow = inf;
for (int i = pre[e]; i; i = pre[to[i ^ 1]])
flow = std::min(flow, val[i]);
for (int i = pre[e]; i; i = pre[to[i ^ 1]])
val[i] -= flow, val[i ^ 1] += flow;
for (int i = pre[e]; i; i = pre[to[i ^ 1]])
ans += cst[i] * (ll)flow;
}
print(ans);

return 0;
}