题意：

给定每个兵营的最大容量，以及第ｉ到第ｊ个兵营至少有多少个士兵，问所有兵营一共至少有多少个士兵？

分析：

差分约束系统，注意

• 第ｉ到第ｊ至少有ｋ个
• 第ｉ到第ｊ最多有最大容量之和个
• 每个兵营至少有０个
• 每个兵营最多有最大容量个

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cmath>

using namespace std;

#define mem(s,a)  memset(s, a, sizeof(s))

typedef long long ll;

const int maxm = 25005, maxn = 1005;

#define INF 0x3ffffffff

struct edge{int u,v;ll w;};

edge e[maxm];

int c[maxn];

long long d[maxn];

int m, n, tot;

bool bellford()

{

    fill(d,d+n+1,INF);

    d[n] = 0;

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

        for(int j = 0; j < tot; j++){

            int u1= e[j].u, v1 = e[j].v;

            if(d[u1]!=INF&&d[v1]-d[u1]>e[j].w){

                 d[v1] = d[u1] + e[j].w;

                 if(i == n)  return false;

            }

        }

    }

    return true;

}

int main (void)

{

    int t;

    while(~scanf("%d%d",&n, &m)){

       mem(c,0);

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

                scanf("%d",&t);

                c[i] = c[i-1] +t;

        }

        int i, j, k;

        tot = 0;

        for(int a = 0; a < m; a++){

            scanf("%d%d%d",&i,&j,&k);

            e[tot++] = (edge){j, i-1, -k};

            e[tot++] = (edge){i-1, j, c[j]-c[i-1]};

        }

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

            e[tot++] = (edge){b, b + 1, c[b + 1] - c[b]};

            e[tot++] = (edge){b+1, b, 0};

        }

       if(bellford()) printf("%I64d\n",d[n]-d[0]);

        else  printf("Bad Estimations\n");

    }

    return 0;

}

之前一直怕k会很大，就用了long long，可是INF忘记改，一直PE，后来改了INF，AC，改成int，AC，可是到现在也不明白为什么是PE而不是WA。

先放着再想想吧。