题目描述  笨笨种了一块西瓜地，但这块西瓜地的种植范围是一条直线的……  笨笨在一番研究过后，得出了m个结论，这m个结论可以使他收获的西瓜最多。  笨笨的结论是这样的：  从西瓜地B处到E处至少要种植T个西瓜，这个范围的收获就可以最大化。  笨笨不想那么辛苦，所以他想种植的西瓜尽量少，而又满足每一个所得的结论。输入格式第一行两个数n,m（0
    
     <=5000,0<=m<=3000），表示笨笨的西瓜地长n，笨笨得出m个结论。接下来m行表示笨笨的m个结论，每行三个数b,e,t（1<=b<=e<=n,0<=t<=e-b+1）。输出格式输出笨笨最少需种植多少西瓜。提示基本上来说，笨笨的西瓜地就是一条壮观的线……笨笨原创。样例数据输入样例 #1 输出样例 #19 41 4 24 6 28 9 23 5 25
    

差分约束系统

习惯用最长路，对于xi-xj>=w 从j向i连w的边

重点是约束关系的推导，比如这题就有隐含条件一个地只能种一个西瓜

//Stay foolish,stay hungry,stay young,stay simple#include
    
     #include
     
      #include
      
       using namespace std;const int MAXN=50000;int n,m;struct Edge{    int next,to,w;}e[MAXN];int ecnt,head[MAXN];inline void add(int x,int y,int w){    e[++ecnt].next = head[x];    e[ecnt].to = y;    e[ecnt].w = w;    head[x] = ecnt;}int val[MAXN];bool inq[MAXN];void spfa(){    for(int i=1;i<=n;i++)        val[i]=-(1<<28);    queue
       
         Q;    Q.push(0);    inq[0]=1;    while(!Q.empty()){        int top=Q.front() ;        Q.pop();inq[top]=0;        for(int i=head[top];i;i=e[i].next){            int v=e[i].to ;            if(val[v]
        
         >n>>m;    for(int i=1;i<=m;i++){        int x,y,w;        cin>>x>>y>>w;        add(x-1,y,w);    }    for(int i=1;i<=n;i++){        add(i-1,i,0);        add(i,i-1,-1);    }    spfa();        cout<