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

14

HINT

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

题解

题目中的式子有点多，我们把它们都写出来：

令第$i$天的总志愿者人数为$P_i$，第$j$种志愿者招募人数为$K_j$，那么有

$$P_i = P_{i-1} + \sum_{S_j=i}K_j - \sum_{T_j=i-1}K_j \geq A_i$$

$P_i \geq A_i$不太好处理，我们把它写成

$$P_i = A_i + B_i (B_i \geq 0)$$

那么我们就有

$$P_i - P_{i-1} = \sum_{S_j=i}K_j - \sum_{T_j=i-1}K_j = A_i + B_i - A_{i-1} - B_{i-1}$$

即

$$\sum_{S_j=i}K_j + B_{i-1} + A_{i-1} =  \sum_{T_j=i-1}K_j + B_i + A_i$$

我们发现，每个志愿者所代表的$K_j$只在$S_j$和$T_j+1$两个式子里出现，而且一左一右，每天的松弛变量$B_i$也只在$i$和$i+1$出现，且一左一右。

而且这个式子很像网络流中的流量平衡：

$$out_i = in_i$$

其中$in_i, out_i$分别是某个点的流入和流出。

这里，

$$in_i = \sum_{T_j=i-1}K_j + B_i + A_i$$

$$out_i = \sum_{S_j=i}K_i + B_{i-1} + A_{i-1}$$

由于$A_i,A_{i-1}$是必须满足的，所以我们将其视为i与S，T之间的边容量，而且一个点既从S流入又向T流出没有意义，我们只需保留容量较大的边，容量为$|A_i-A_{i-1}|$。

那么，现在有$n+3$个点，即源点，汇点，第一天到第$n+1$天的点（若没有第$n+1$天，那么某些$K_j$不会出现两次），边有三种：

1.$K_j$对应的边，由$S_j$连向$T_j+1$，单位代价$C_j$，容量$\infty$。

2.$B_i$对应的边，由$i+1$连向$i$，单位代价$0$，容量$\infty$。

3.$A_i-A_{i-1}$对应的边，由$S$连向$i$或由$i$连向$T$，单位代价$0$，容量$|A_i-A_{i-1}|$。

最后求一遍最小费用最大流，则每条种类为1的边流量即为此种志愿者招募个数，种类为2的边流量即为该天比要求多多少，种类为3的边均满流（否则无解）。

输出费用即可。

附代码：

#include 
     
      #include 
      
       #include 
       
        using std::queue;typedef long long LL;const LL INF = 10000000000000000;const int N = 1050;const int M = 100050;struct MCMF{  int to[M];  LL cost[M], ret[M];  int pre[N], nxt[M], cnt;  LL dis[N];  int las[N];  bool inQ[N];  queue
        
          Q;  MCMF() {    std::fill(pre, pre + N, -1);    cnt = 0;  }  inline void addEdge(int u, int v, LL w, LL c) {    to[cnt] = v, cost[cnt] = w, ret[cnt] = c;    nxt[cnt] = pre[u], pre[u] = cnt++;    to[cnt] = u, cost[cnt] = -w, ret[cnt] = 0;    nxt[cnt] = pre[v], pre[v] = cnt++;  }  bool SPFA(int s, int t) {    std::fill(dis, dis + N, INF);    std::fill(inQ, inQ + N, 0);    dis[s] = 0;    inQ[s] = true;    while (!Q.empty()) Q.pop();    Q.push(s);    while (!Q.empty()) {      int x = Q.front(); Q.pop();      inQ[x] = false;      for (int i = pre[x]; ~i; i = nxt[i]) if (ret[i]) {        int v = to[i];        if (dis[v] > dis[x] + cost[i]) {          dis[v] = dis[x] + cost[i];          las[v] = i;          if (!inQ[v]) {            inQ[v] = true;            Q.push(v);          }        }      }    }    return dis[t] < INF;  }  LL solve(int s, int t) {    LL ans = 0;    while (SPFA(s, t)) {      LL p = INF;      for (int i = t; i != s; i = to[las[i] ^ 1])        p = std::min(p, ret[las[i]]);      ans += p * dis[t];      for (int i = t; i != s; i = to[las[i] ^ 1]) {        ret[las[i]] -= p;        ret[las[i] ^ 1] += p;      }    }    return ans;  }};MCMF solver;int A[N];int main() {  int n, m, a, b, c;  scanf("%d%d", &n, &m);  int S = 0, T = n + 2;  for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);  for (int i = 0; i < m; ++i) {    scanf("%d%d%d", &a, &b, &c);    solver.addEdge(a, b + 1, c, INF);  }  for (int i = 1; i <= n + 1; ++i) {    int t = A[i] - A[i - 1];    if (t >= 0) solver.addEdge(S, i, 0, t);    else solver.addEdge(i, T, 0, -t);    if (i > 1) solver.addEdge(i, i - 1, 0, INF);  }  printf("%lld\n", solver.solve(S, T));  return 0;}