Description

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

Input

第一行包含两个整数 \(n, m\), 表示完成项目的天数和可以招募的志愿者的种类.

接下来的一行中包含 \(n\) 个非负整数 \(d_i\), 表示每天至少需要的志愿者人数.

接下来的 \(m\) 行中每行包含三个整数 \(s_i, t_i, c_i\), 含义如上文所述.

为了方便起见, 我们可以认为每类志愿者的数量都是无限多的.

Output

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

Sample Input

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

Sample Output

14

Data Range

对于所有数据, 满足:\(1 \leq n \leq 1000, 1 \leq m \leq 10000\), 题目中其他所涉及的数据均不超过 \(2^{31}-1\).

Explanation

把每个志愿者工作的时间段当作一个区间, 于是把一个两个维度的问题压到了一个维度上 (雾). 由于涉及两组信息, 我们可以建一个费用流图, 具体建法如下:

  • 对于每一个志愿者, 连接一条边 \((s_i \rightarrow t_i+1, \infty, c_i)\);
  • 对于 \([1, n+1]\) 中的任何一个整数 \(i\), 若 \(d_i \geq d_{i-1}\), 则连接边 \((S \rightarrow i, d_i - d_{i-1}, 0)\);
  • 反之, 若 \(d_i \lt d_{i-1}\), 则连接边 \((i \rightarrow T, d_{i-1} - d_i, 0)\).

然后求出满流情况下的最小费用即可.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

#define nullptr NULL
using namespace std;
typedef long long lli;
const int maxn = 10010, maxm = 100100;
const lli infinit = 0x007f7f7f7f7f7f7fll;

class SpfaMaxflow
{
public:
    struct edge
    {
        int u, v;
        lli flow, cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm], *from[maxn];
    void add_edge(int u, int v, lli flow, lli cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0, q->cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool inque[maxn];
    lli dist[maxn];
    bool bfs(void)
    {
        queue<int> que;
        for (int i = 0; i <= n; i++)
            inque[i] = false, dist[i] = infinit, from[i] = nullptr;
        que.push(s); inque[s] = true;
        dist[s] = 0;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && dist[p] + ep->cost < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->cost;
                    from[ep->v] = ep;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            inque[p] = false;
        }
        if (dist[t] >= infinit)
            return false;
        return true;
    }
    lli max_flow, min_cost;
    void eval(void)
    {
        max_flow = min_cost = 0;
        while (bfs()) {
            lli tmp = infinit;
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                tmp = min(tmp, ep->flow);
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                ep->flow -= tmp,
                ep->rev->flow += tmp;
            max_flow += tmp;
            min_cost += dist[t] * tmp;
        }
        return ;
    }
} graph;

int n, m;
lli d[maxn], s[maxn], t[maxn], c[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &d[i]);
    for (int i = 1; i <= m; i++)
        scanf("%lld%lld%lld", &s[i], &t[i], &c[i]);
    // Constructing graph
    graph.n = n + 2;
    graph.s = 0;
    graph.t = graph.n;
    for (int i = 1; i <= m; i++)
        graph.add_edge(s[i], t[i] + 1, infinit, c[i]);
    for (int i = 1; i <= n + 1; i++) {
        int tmp = d[i] - d[i - 1];
        if (tmp >= 0)
            graph.add_edge(graph.s, i, tmp, 0);
        else
            graph.add_edge(i, graph.t, -tmp, 0);
        graph.add_edge(i, i - 1, infinit, 0);
    }
    graph.eval();
    lli cost = graph.min_cost;
    printf("%lld\n", cost);
    return 0;
}