- 1#include 2#include 3#include 4#include 5#include 6#include 7#include 8#include 9#include 10#include < set > 11#define MAXX 11003 12#define INF 99999999 13 using namespace std;
- 14 struct edge {
- 15 int nxt,
- to,
- c,
- w;
- 16
- }
- e[MAXX * 4];
- 17 int head[MAXX],
- pre[MAXX],
- dis[MAXX],
- in[MAXX],
- n,
- m,
- x,
- cc,
- tt,
- ss,
- ans,
- tot;
- 18 void add(int from, int to, int c, int w) {
- 19 e[tot].nxt = head[from];
- 20 e[tot].to = to;
- 21 e[tot].w = w;
- 22 e[tot].c = c;
- 23 head[from] = tot++;
- 24
- }
- 25 void ADD(int from, int to, int c, int w) {
- 26 add(from, to, c, w);
- 27 add(to, from, 0, -w);
- 28
- }
- 29 bool SPFA(int s, int t) {
- 30 queue < int > que;
- 31
- while (!que.empty()) que.pop();
- 32
- for (int i = 1; i <= n + 3; ++i) dis[i] = INF,
- in[i] = false;
- 33 que.push(s); in [s] = true;
- dis[s] = 0;
- 34
- while (!que.empty()) {
- 35 int u = que.front();
- 36
- for (int i = head[u]; i != -1; i = e[i].nxt) 37
- if (e[i].c > 0 && dis[e[i].to] > dis[u] + e[i].w) {
- 38 int v = e[i].to;
- 39 dis[v] = dis[u] + e[i].w;
- 40 pre[v] = i;
- 41
- if (!in [v]) in [v] = true,
- que.push(v);
- 42
- }
- 43 in [u] = false;
- 44 que.pop();
- 45
- }
- if (dis[t] == INF) return false;
- 46 int u,
- p,
- sum = INF;
- 47
- for (u = t; u != s; u = e[p ^ 1].to) 48 p = pre[u],
- sum = min(sum, e[p].c);
- 49
- for (u = t; u != s; u = e[p ^ 1].to) {
- 50 p = pre[u];
- 51 e[p].c -= sum,
- e[p ^ 1].c += sum;
- 52 ans += sum * e[p].w;
- 53
- }
- return true;
- 54
- }
- 55 int mincostflow(int s, int t) {
- 56
- while (SPFA(s, t));
- 57
- return ans;
- 58
- }
- 59 int main() {
- 60 memset(head, -1, sizeof(head));
- 61 scanf("%d%d", &n, &m);
- 62
- for (int i = 1; i <= n; ++i) 63
- if (i != 1 && i != n) {
- 64 scanf("%d", &x);
- 65 ADD(i, i + 1, INF - x, 0);
- 66
- } else if (i == 1) {
- int x;
- 67 scanf("%d", &x);
- 68 ADD(0, 1, INF, 0);
- 69 ADD(1, 2, INF - x, 0);
- 70
- } else {
- 71 scanf("%d", &x);
- 72 ADD(n, n + 1, INF - x, 0);
- 73 ADD(n + 1, n + 2, INF, 0);
- 74
- }
- 75
- for (int i = 1; i <= m; ++i) {
- 76 scanf("%d%d%d", &ss, &tt, &cc);
- 77 ADD(ss, tt + 1, INF, cc);
- 78
- }
- 79 printf("%d", mincostflow(0, n + 2));
- 80
- return 0;
- 81
- }
来源: http://www.bubuko.com/infodetail-2005569.html