INTERVAL - Intervals

• 题目描述：有n个区间，在区间[ai，bi]中至少取任意互不相同的ci个整数。求在满足n个区间的情况下，至少要取多少个正整数。
• 思路:运用前缀和思想，s[i]表示[0,i]最少取多少个数，条件[i,j]取k个数则可以表示成s[j]-s[i-1]>=k,同时考虑i与i-1的限制条件，0<=s[i]-s[i-1]<=1,考虑到0的时候会出现-1，把所有点的编号+1即可，其余按照差分约束建图，求最大值。
• 隐含限制条件：可以证明对隐含限制条件连边在图中有实际意义，0权边使得整个图连通，-1权值边防止出现局部不合理的情况（经提交测试确有）；
• 启示：不能凭感觉忽略隐性的限制条件，要把这些条件在图中表达完整。

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
int t,n,m,cnt,last[50005],x,y,z,d[50005];
bool inq[50005],tmp;
struct edge{
    int v,w,next;
}e[151000];
inline void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=last[u];
    last[u]=cnt;
}
void spfa()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    d[i]=-1;
    d[0]=0;
    q.push(0);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=last[u];i;i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if(d[u]+w>d[v])
            {
                d[v]=d[u]+w;
                if(!inq[v])
                {
                    inq[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
void intt()
{
    for(int i=1;i<=cnt;i++)
    e[i].w=e[i].v=e[i].next=0;
    memset(last,0,sizeof(last));
    memset(inq,0,sizeof(inq));
    n=cnt=0;
}
int main()
{
    cin>>t;
    while(t--)
    {
        if(tmp)
        cout<<endl;
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            x++;y++;
            n=max(n,y);
            add(x-1,y,z);
        }
        for(int i=1;i<=n;i++)
        {
            add(i-1,i,0);
            add(i,i-1,-1);
        }
        spfa();
        cout<<d[n]<<endl;
        tmp=1;
        intt();
    }
    return 0;
}