描述

传送门：洛谷-p1645

有一个整数序列，它的每个数各不相同，我们不知道它的长度是多少（即整数个数），但我们知道在某些区间中间至少有多少个整数，用区间（Li,Ri,Ci）来描述，表示这个整数序列中至少有Ci个数来自区间[Li,Ri]，给出若干个这样的区间，问这个整数序列的长度最少能为多少？

Input

第一行一个整数$N$，表示区间个数；
接下来$N$行，每行三个整数$（L_i,R_i,C_i）$，描述一个区间。

【数据规模】
$N<=1000,\ \ \ 0<=L_i<=R_i<=1000,\ \ \ 1<=C_i<=R_i-L_i+1$

Output

仅一个数，表示该整数序列的最小长度。

Examples

intput
1
2
3
4
5
4
4 5 1
6 10 3
7 10 3
5 6 1
output
1
4

思路

这是一道裸的差分约束，对于给的每个区间：$[L,R]$中至少有$c$个,连一条长为c的边从节点L-1指向节点R。为了能从0走到最大的节点，我们连一条长为0的边从节点i-1指向i.连一条长为-1的边从节点i指向i-1，这样图就建好了，最后用SPFA跑一个最长路。

由于是跑最长路，所以这些负权的环不会造成死循环。

用链式向前星存边，邻接矩阵可能要爆内存。

代码

#include<bits/stdc++.h>
using namespace std;
#define CRL(a,x) memset(a,x,sizeof(a))

int Begin[5005],N,n,Dis[1005],Vis[1005]={0}; //注意边的数量
struct node{int To,S,Next;};
vector<node> Edge;

void add(int x,int y,int z){
    node tem=(node){y,z,Begin[x]};
    Begin[x]=Edge.size();
    Edge.push_back(tem);
}

void Spfa(int s){
    queue<int> Q;
    CRL(Dis,-63);Dis[s]=0;
    Q.push(s);Vis[s]=1;
    while(!Q.empty()){
        int tem=Q.front();Q.pop();Vis[tem]=0;
        for(int i=Begin[tem];~i;i=Edge[i].Next){
            if(Dis[Edge[i].To]<Dis[tem]+Edge[i].S){
                Dis[Edge[i].To]=Dis[tem]+Edge[i].S;
                if(!Vis[Edge[i].To]){
                    Q.push(Edge[i].To);
                    Vis[Edge[i].To]=1;
                }
            }
        }
    }
}

int main(){
    int a,b,s;
    CRL(Begin,-1);
    cin>>N;
    while(N--){
        cin>>a>>b>>s;
        add(a-1,b,s);           //连一条长为s的边从节点a-1指向节点b
        n=max(n,b);
    }

    for(int i=1;i<=n;i++){
        add(i-1,i,0);       //连一条长为0的边从节点i-1指向i
        add(i,i-1,-1);      //连一条长为-1的边从节点i指向i-1
    }

    Spfa(0);
    cout<<Dis[n]<<endl;
    return 0;
}