BZOJ 1061: [Noi2008]志愿者招募

Description

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。

布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

Input

第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。

Output

仅包含一个整数，表示你所设计的最优方案的总费用。

Sample Input

3 3

2 3 4

1 2 2

2 3 5

3 3 2

Sample Output

HINT

1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均不超过2^31-1。

Solution

根据每一天的信息，加入松弛变量列出N个方程，让第0个方程和第N+1个方程为0=0，相邻方程相减，一共有N+1个方程。然后移项。

把每个方程看成一个点。左边为流入的，右边为流出的，可以发现每个变量在左边出现一次，右边出现一次。然后根据这些方程建出网络流模型来，目标可以看成是一个最小费用最大流，跑一遍网络流就好了。

Code

 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
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = ~0ull>>3;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
struct edge_type {
    int to, next;
    LL r, c;
} edge[500009];
int cnte = 1, h[5005];
void ins(int x, int y, LL r, LL c) {
    edge[++cnte].to = y;
    edge[cnte].next = h[x];
    edge[cnte].r = r;
    edge[cnte].c = c;
    h[x] = cnte;
    edge[++cnte].to = x;
    edge[cnte].next = h[y];
    edge[cnte].r = 0;
    edge[cnte].c = -c;
    h[y] = cnte;
}
int n, m, S, T;
int A[5005], pre[5005];
LL dis[5005], a[5005];
queue<int> Q;
bool vis[5005];
bool SPFA(LL &flow, LL &cost) {
    for (int i = S; i <= T; ++i) {
        dis[i] = INF;
    }
    a[S] = INF; dis[S] = 0; Q.push(S); vis[S] = true;
    int now;
    while (!Q.empty()) {
        now = Q.front(); vis[now] = false; Q.pop();
        for (int i = h[now]; i; i = edge[i].next) {
            if (!edge[i].r) continue;
            if (dis[edge[i].to] > dis[now] + edge[i].c) {
                pre[edge[i].to] = i;
                dis[edge[i].to] = dis[now] + edge[i].c;
                a[edge[i].to] = min(a[now], edge[i].r);
                if (!vis[edge[i].to]) {
                    vis[edge[i].to] = true;
                    Q.push(edge[i].to);
                }
            }
        }
    }
    if (dis[T] == INF)
        return false;
    flow += a[T];
    cost += a[T] * dis[T];
    for (now = T; now != S; now = edge[pre[now]^1].to) {
        edge[pre[now]].r -= a[T];
        edge[pre[now]^1].r += a[T];
    }
    return true;
}
LL MCMF() {
    LL flow = 0, cost = 0;
    while (SPFA(flow, cost));
    return cost;
}
int main() {
    n = getint(); m = getint();
    S = 0; T = n + 2;
    int x, y, z;
    for (int i = 1; i <= n; ++i) {
        A[i] = getint();
        ins(i, i+1, INF, 0);
        if (A[i] - A[i-1] > 0)
            ins(i, T, A[i] - A[i-1], 0);
        else
            ins(S, i, A[i-1] - A[i], 0);
    }
    ins(S, n + 1, A[n], 0);
    for (int i = 1; i <= m; ++i) {
        x = getint(); y = getint(); z = getint();
        ins(y+1, x, INF, z);
    }
    LL ans = MCMF();
    printf("%lld", ans);
    return 0;
}