志愿者招募
题目描述
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难
题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要
Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用
是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这
并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
输入
第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负
整数，表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了
方便起见，我们可以认为每类志愿者的数量都是无限多的。
输出
仅包含一个整数，表示你所设计的最优方案的总费用。
样例输入
3 3
2 3 4
1 2 2
2 3 5
3 3 2
样例输出
14
提示
1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均 不超过2^31-1
题解个人觉得这篇写得挺好的（其实因为自己也没有完全弄清楚+懒qwqq: 点击我看题解(*/ω＼*)
蒟蒻的超慢代码：
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue> const int Maxv = , INF = 0x6ffffff, M = ;
int Head[Maxv], d[Maxv], from[Maxv], cost[Maxv], a[Maxv], s, n, m, t, cnt = ;
bool inq[Maxv];
struct edge{
int from, to, w, c, next;
}e[Maxv << ]; inline int read(){
int x = , f = ;
char c = getchar();
while (c < '' || c > '') {
if (c == '-') {
f = -;
}
c = getchar();
}
while (c >= '' && c <= '') {
x = x * + c - '';
c = getchar();
}
return x * f;
} void Add(int u, int v, int w, int c){
cnt++;
e[cnt].from = u;
e[cnt].to = v;
e[cnt].w = w;
e[cnt].c = c;
e[cnt].next = Head[u];
Head[u] = cnt;
} void Add_Edge(int u, int v, int w, int c){
Add(u, v, w, c);
Add(v, u, , -c);
} bool spfa(){
for (int i = ; i <= t; i++) {
d[i] = INF;
}
memset(inq, false, sizeof(inq));
std::queue<int> Q;
Q.push(s);
d[s] = ;
inq[s] = true;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
inq[u] = false;
for (int i = Head[u]; i; i = e[i].next) {
if (e[i].w > && d[e[i].to] > d[u] + e[i].c) {
d[e[i].to] = d[u] + e[i].c;
from[e[i].to] = i;
if (!inq[e[i].to]) {
Q.push(e[i].to);
inq[e[i].to] = true;
}
}
}
}
return d[t] != INF;
} int MCMF(){
int Ans = ;
while (spfa()) {
int x = INF;
for (int i = from[t]; i; i = from[e[i].from]) {
x = std::min(x, e[i].w);
}
Ans += d[t] * x;
for (int i = from[t]; i; i = from[e[i].from]) {
e[i].w -= x;
e[i ^ ].w += x;
}
}
return Ans;
} int main(){
memset(Head, , sizeof(Head));
int x, y, ans;
n = read();
m = read();
s = n + ;
t = s + ;
for (int i = ; i <= n; i++) {
a[i] = read();
}
for (int i = ; i <= m; i++) {
x = read();
y = read();
cost[i] = read();
Add_Edge(x, y + , INF, cost[i]);
}
a[] = a[n + ] = ;
for (int i = ; i <= n + ; i++) {
int tmp = a[i] - a[i - ];
if (tmp >= ) {
Add_Edge(s, i, tmp, );
}
else {
Add_Edge(i, t, -tmp, );
}
}
for (int i = ; i <= n; i++) {
Add_Edge(i + , i, INF, );
}
printf("%d\n", MCMF());
return ;
}