有n个营地，每一个营地至多容纳Ci人。给出m个条件：第i到第j个营地之间至少有k人。

问n个营地总共至少有多少人。

此题显然差分约束。要求最小值。则建立x-y>=z方程组，建图求最长路。

用d[i]表示[1,i]个帐篷中一共多少人。依据题意可得到不等关系：

1、0<=d[i]-d[i-1]<=C[i]

2、d[j]-d[i]>=k

此外，我们加入0为附加结点，则0到其它点也要建边。

再求解0为源点的最长路就可以。

我的坑点是，判负环返回0。否则返回d[n]。

而d[n]本身就可能是0。

这里要注意下

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#define inf 0x3f3f3f3f

#define eps 1e-6

#define ll __int64

#define maxm 20010

#define maxn 1010

using namespace std;

struct node

{

    int v,w,next;

}e[maxm];

int head[maxn],d[maxn],inq[maxn],outq[maxn],n,m,h;

void init()

{

    memset(head,-1,sizeof head);

    h=0;

}

void addedge(int a,int b,int c)

{

    e[h].v=b;

    e[h].w=c;

    e[h].next=head[a];

    head[a]=h++;

}

int spfa(int st)

{

    memset(inq,0,sizeof inq);

    memset(outq,0,sizeof outq);

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

        d[i]=-0xFFFFFF;

    d[st]=0;

    inq[st]=1;

    queue<int> q;

    q.push(st);

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        inq[x]=0;

        outq[x]++;

        if(outq[x]>n) return 0;//存在负环

        for(int i=head[x];i!=-1;i=e[i].next)

        {

            if(d[e[i].v]<d[x]+e[i].w)

            {

                d[e[i].v]=d[x]+e[i].w;

                if(!inq[e[i].v])

                {

                    inq[e[i].v]=1;

                    q.push(e[i].v);

                }

            }

        }

    }

    return 1;

}

int main()

{

    int a,b,c;

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

    {

        init();

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

        {

            scanf("%d",&c);

            addedge(i-1,i,0);

            addedge(i,i-1,-c);

            addedge(0,i,0);//全部边与附加结点0相连

        }

        for(int i=0;i<m;i++)

        {

            scanf("%d%d%d",&a,&b,&c);

            addedge(a-1,b,c);

        }

        int ans=spfa(0);

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

       //     printf("%d ",d[i]);

       // puts("");

        if(ans==0)

            printf("Bad Estimations\n");

        else printf("%d\n",d[n]);

    }

    return 0;

}