题意：

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

分析：

差分约束系统，注意

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

代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define mem(s,a)  memset(s, a, sizeof(s))typedef long long ll;const int maxm = 25005, maxn = 1005;#define INF 0x3ffffffffstruct 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。

先放着再想想吧。