danihao123's Blog

膜了一发BYVoid的题解……竟然搞懂了

这首先是个非常简单的线性规划，就是有若干限制（每天要求的志愿者），形如：

\[P_i = X_a + X_b +\ldots + X_c\geq A_i\]

（这里用\(X_i\)表示第\(i\)类志愿者雇佣了多少个，\(P_i\)表示第\(i\)天的志愿者总数，\(A_i\)同原题面）

且最小化总费用。

既然我们我知道\(P_i\geq A_i\)，那么说明\(P_i\)一定可以表示为\(A_i + Y_i\)（\(Y_i\geq 0\)）。然后这样限制就变成了：

\[P_i = X_a + X_b +\ldots + X_c + Y_i = A_i\]

这个长得很像可以流量平衡的样子，但是流量的变动是表示不了的……

然后假设\(P_0 = 0\)且\(P_{n + 1} = 0\)，这样就可以对限制差分一下，我们就有了\(n + 1\)个限制，然后这个式子就可以流量平衡做了（因为不考虑常数项的话，同一变量只可能在两个限制中出现，并且一正一负，这样就可以通过一个限制送给另一个限制流量来表示了。至于常数项，通过源或者汇连边即可表达）。

然后由于志愿者无限，所以这个东西也一定有解……

我局的我这么渣各位看官看懂的可能性基本上是零……还是推荐BYVoid神犇的题解，比我透彻多了。

代码：

/**************************************************************
    Problem: 1061
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3164 ms
    Memory:6824 kb
****************************************************************/
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
#include <cassert>
typedef long long ll;
int m, n;
const int maxno = 100005;
const int maxe = 100005;
int first[maxno];
int next[maxe], from[maxe], to[maxe]; ll flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, ll f, ll c) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  from[gcnt] = u; to[gcnt] = v;
  cap[gcnt] = f; flow[gcnt] = 0;
  cost[gcnt] = c;
}
int rev(int i) {
  return ((i - 1) ^ 1) + 1;
}
int ins_edge(int u, int v, ll f, ll c = 0LL) {
#ifdef LOCAL
  printf("Inserting Edge (%d, %d, %lld, %lld)\n", u, v, f, c);
#endif
  add_edge(u, v, f, c);
  add_edge(v, u, 0, -c);
  return gcnt - 1;
}
 
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
int tot;
bool spfa(int s, int t, ll &f, ll &c) {
  static ll d[maxno];
  static bool inq[maxno];
  static ll a[maxno]; static int p[maxno];
  std::fill(d, d + tot + 1, LINF);
  std::fill(inq, inq + tot + 1, false);
  std::fill(a, a + tot + 1, 0LL);
  std::fill(p, p + tot + 1, 0);
  d[s] = 0;
  std::queue<int> Q; Q.push(s); inq[s] = true;
  a[s] = LINF;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    inq[u] = false;
    for(int i = first[u]; i; i = next[i]) {
      if(cap[i] > flow[i]) {
        int v = to[i];
        if(d[v] > d[u] + cost[i]) {
          d[v] = d[u] + cost[i];
          a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
          if(!inq[v]) {
            Q.push(v); inq[v] = true;
          }
        }
      }
    }
  }
  if(a[t] == 0LL) return false;
  f += a[t];
  c += a[t] * d[t];
  for(int e = p[t]; e; e = p[from[e]]) {
    flow[e] += a[t];
    flow[rev(e)] -= a[t];
  }
  return true;
}
void mcmf(int s, int t, ll &f, ll &c) {
  while(spfa(s, t, f, c));
}
 
const int maxn = 1005, maxm = 10005;
int E[maxn];
int A[maxn], D[maxn];
int main() {
  scanf("%d%d", &n, &m);
  int s = 0, t = n + 2; tot = n + 2;
  for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
  for(int i = 1; i <= n + 1; i ++) {
    D[i] = A[i] - A[i - 1];
    if(D[i] >= 0) {
      E[i] = ins_edge(s, i, D[i]);
    } else {
      E[i] = ins_edge(i, t, -D[i]);
    }
  }
  for(int i = 1; i <= n; i ++) {
    ins_edge(i + 1, i, LINF);
  }
  while(m --) {
    int S, T, C; scanf("%d%d%d", &S, &T, &C);
    ins_edge(S, T + 1, LINF, C);
  }
  ll f = 0, c = 0; mcmf(s, t, f, c);
  printf("%lld\n", c);
  return 0;
}