- 1#include 2#include 3#include 4#include 5#include 6 //by NeighThorn
- 7#define inf 0x3f3f3f3f 8#define INF 0x3f3f3f3f3f3f 9 using namespace std;
- 10 11 const int maxn = 1000 + 5,
- maxm = 100000 + 5;
- 12 13 int n,
- m,
- S,
- T,
- cnt,
- w[maxm],
- hd[maxn],
- fl[maxm],
- to[maxm],
- nxt[maxm],
- Min[maxn],
- vis[maxn],
- from[maxn];
- 14 15 long long dis[maxn],
- dif[maxn];
- 16 17 inline bool spfa(void) {
- 18
- for (int i = S; i <= T; i++) 19 dis[i] = INF,
- Min[i] = inf;
- 20 queue < int > q;
- q.push(S),
- vis[S] = 1,
- dis[S] = 0;
- 21
- while (!q.empty()) {
- 22 int top = q.front();
- q.pop();
- vis[top] = 0;
- 23
- for (int i = hd[top]; i != -1; i = nxt[i]) 24
- if (dis[to[i]] > dis[top] + w[i] && fl[i]) {
- 25 from[to[i]] = i;
- 26 dis[to[i]] = dis[top] + w[i];
- 27 Min[to[i]] = min(Min[top], fl[i]);
- 28
- if (!vis[to[i]]) 29 vis[to[i]] = 1,
- q.push(to[i]);
- 30
- }
- 31
- }
- 32
- return dis[T] != INF;
- 33
- }
- 34 35 inline long long find(void) {
- 36
- for (int i = T; i != S; i = to[from[i] ^ 1]) 37 fl[from[i]] -= Min[T],
- fl[from[i] ^ 1] += Min[T];
- 38
- return dis[T] * Min[T];
- 39
- }
- 40 41 inline int dinic(void) {
- 42 int res = 0;
- 43
- while (spfa()) 44 res += find();
- 45
- return res;
- 46
- }
- 47 48 inline void add(int l, int s, int x, int y) {
- 49 w[cnt] = l;
- fl[cnt] = s;
- to[cnt] = y;
- nxt[cnt] = hd[x];
- hd[x] = cnt++;
- 50 w[cnt] = -l;
- fl[cnt] = 0;
- to[cnt] = x;
- nxt[cnt] = hd[y];
- hd[y] = cnt++;
- 51
- }
- 52 53 signed main(void) {
- 54 // freopen("in.txt","r",stdin);
- 55 memset(hd, -1, sizeof(hd));
- 56 scanf("%d%d", &n, &m);
- S = 0,
- T = n + 2;
- 57
- for (int i = 1, y; i <= n; i++) 58 scanf("%d", &y),
- add(0, inf, i, i + 1),
- dif[i] -= y,
- dif[i + 1] += y;
- 59
- for (int i = 1, s, x, y; i <= m; i++) 60 scanf("%d%d%d", &x, &y, &s),
- add(s, inf, y + 1, x);
- 61
- for (int i = 1; i <= n + 1; i++) {
- 62
- if (dif[i] > 0) 63 add(0, dif[i], S, i);
- 64
- else if (dif[i] < 0) 65 add(0, -dif[i], i, T);
- 66
- }
- 67 printf("%d\n", dinic());
- 68
- return 0;
- 69
- }
来源: