http://www.lydsy.com/JudgeOnline/problem.php?id=1061

https://vijos.org/p/1825

直接上姜爷论文。。。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 1013;

const int M = 40003;

const int inf = 0x7fffffff;

struct node {int nxt, to, c, w, from;} E[M];

int cnt = 1, point[N << 1];

void ins(int u, int v, int c, int w) {

	E[++cnt] = (node) {point[u], v, c, w, u}; point[u] = cnt;

	E[++cnt] = (node) {point[v], u, 0, -w, v}; point[v] = cnt;

}

bool inq[N];

int dist[N], pre[N], q[N];

bool spfa(int s, int t) {

	for (int i = s; i <= t; ++i) dist[i] = inf, pre[i] = 0;

	int u, v, tt, head = 0, tail = 1; q[1] = s; inq[s] = true; dist[s] = 0;

	while (head != tail) {

		++head; if (head == N) head = 0;

		u = q[head]; inq[u] = false;

		for (int i = point[u]; i; i = E[i].nxt)

			if (E[i].c && dist[v = E[i].to] > (tt = dist[u] + E[i].w)) {

				dist[v] = tt; pre[v] = i;

				if (!inq[v]) {

					inq[v] = true;

					++tail; if (tail == N) tail = 0;

					q[tail] = v;

				}

			}

	}

	return dist[t] != inf;

}

ll MCMF(int s, int t) {

	ll ret = 0;

	while (spfa(s, t)) {

		int f = inf;

		for (int u = t; u != s; u = E[pre[u]].from) f = min(f, E[pre[u]].c);

		for (int u = t; u != s; u = E[pre[u]].from) E[pre[u]].c -= f, E[pre[u] ^ 1].c += f;

		ret += f * dist[t];

	}

	return ret;

}

int n, m, s, t, c, S, T, a[N];

int main() {

	scanf("%d%d", &n, &m);

	S = 0; T = n + 2;

	for (int i = 1; i <= n; ++i) scanf("%d", a + i);

	for (int i = 0; i <= n; ++i) {

		int num = a[i + 1] - a[i];

		if (num < 0) ins(i + 1, T, -num, 0);

		if (num > 0) ins(S, i + 1, num, 0);

	}

	for (int i = 1; i <= n; ++i) ins(i + 1, i, inf, 0);

	for (int i = 1; i <= m; ++i) {

		scanf("%d%d%d", &s, &t, &c);

		ins(s, t + 1, inf, c);

	}

	printf("%lld\n", MCMF(S, T));

	return 0;

}