题目地址：洛谷：【P3980】[NOI2008]志愿者招募 – 洛谷、BZOJ：Problem 1061. — [Noi2008]志愿者招募

题目描述

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

题意简述

有$n$天工作，每一天需要至少$a_i$人，有$m$批人，每一批有无限多人，第$i$批可以从$s_i$天工作到$t_i$天，雇一个人需要$c_i$开销，求开销最小的方案。

输入输出格式

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

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

输入输出样例

输入样例#1：

3 3
2 3 4
1 2 2
2 3 5
3 3 2

输出样例#1：

14

说明

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

题解

考虑最小费用最大流。从第$i$天向第$i+1$天的点建边容量为$INF-a_i$费用$0$，而每一批人从$s_i$向$t_i+1$建边容量为$INF$费用$c_i$，由于保证有解所以一定能跑满$INF$的流，此处即是把每一天对应的流量转到了雇佣的人的边上去了。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

const int MAXN = 1005, INF = 1e9;

int n, m;

struct Edge {
    int to, cap, cost, nxt;
} gra[1000005];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap, int cost) {
    gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}

int dis[MAXN], f[MAXN], pre[MAXN], pree[MAXN];
bool inque[MAXN];
std::queue<int> que;

inline bool spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    memset(f, 0, sizeof(f));
    que.push(s); dis[s] = 0; f[s] = INF; inque[s] = true;
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(dis[v] > dis[u] + gra[i].cost && gra[i].cap) {
                dis[v] = dis[u] + gra[i].cost;
                f[v] = std::min(f[u], gra[i].cap); pre[v] = u; pree[v] = i;
                if(!inque[v]) {
                    inque[v] = true; que.push(v);
                }
            }
        }
    }
    return f[t];
}

int flow, cost;

inline void mcmf(int s, int t) {
    while(spfa(s, t)) {
        flow += f[t]; cost += f[t] * dis[t];
        for(int i = t; i != s; i = pre[i]) {
            gra[pree[i]].cap -= f[t];
            gra[pree[i] ^ 1].cap += f[t];
        }
    }
}

int S, T;

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint(); S = 0; T = n + 1;
    for(int i = 1; i <= n; i++) {
        int t = readint();
        addedge(i, i + 1, INF - t, 0);
    }
    addedge(S, 1, INF, 0);
    for(int i = 1; i <= m; i++) {
        int s = readint(), t = readint(), c = readint();
        addedge(s, t + 1, INF, c);
    }
    mcmf(S, T);
    printf("%d", cost);
    return 0;
}