原题链接

题解

1.设 \(f(i)\) 为 \([0,i]\) 区间内该有多少个数属于整数集 \(Z\)
则对于每一对输入的 \(x,y,c\) 都有 \(f[y]-f[x-1]>=c\) 而且 \(0<=f[i]-f[i-1]<=1\) 差分约束由此得来
又因为下标从零开始，而且我们需要建立超级源点，所以我们把 \(f\) 内的下标整体往右移两位

code

#include<bits/stdc++.h>
using namespace std;
int dis[500005]={0};
int in_q[500005]={0};
struct node
{
    int to,val;
};
vector<node> G[500005];
int main()
{

    int n;
    while(cin>>n)
    {
        for(int i=0;i<=50005;i++) G[i].clear();

    for(int i=1;i<=n;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        G[x+1].push_back(node{y+2,c});
    }

    for(int i=1;i<=50005;i++)
    {
        G[0].push_back(node{i,0});
        G[i].push_back(node{i+1,0});
        G[i+1].push_back(node{i,-1});
    }

    for(int i=1;i<=50005;i++) dis[i]=-2e9;
    memset(in_q,0,sizeof in_q);
    queue<int> q;
    q.push(0);
    in_q[0]=1;
    dis[0]=0;
    while(q.size())
    {
        int now=q.front();
        q.pop();
        in_q[now]=0;
        for(auto next:G[now])
        {
            int to=next.to,val=next.val;
            if(val+dis[now]>dis[to])
            {
                dis[to]=val+dis[now];
                if(!in_q[to])
                {
                    q.push(to);
                    in_q[to]=1;
                }
            }
        }
    }

    int ans=0;
    for(int i=0;i<=50005;i++)
    {
        //if(i<20) printf("%d:%d\n",i-2,dis[i]);
        ans=max(ans,dis[i]-dis[1]);
    }
    cout<<ans<<endl;
    }

    return 0;
}