差分约束系统介绍 http://imlazy.ycool.com/post.1702305.html

设S[i]为数组Z在[0,i)上包含的数的个数,则对每一组a b c有,S[b+1]-S[a]>=c 即 S[a]-S[b+1]<=-c,建图时对应从S[b+1]到S[a]的一条权为-c的边.同时有隐含条件0<=S[i+1]-S[i]<=1即S[i+1]-S[i]<=1和S[i]-S[i+1]<=0,对应建图.

因为本题求的是可行解组中最小的,所以用最长路径求法.

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define maxn 50001
#define inf 0x3f3f3f3f
int n,m,tot;
struct Edge{int w,wt,next;}e[4*maxn];
int start[maxn];
int d[maxn];//单源距离

void add(int v,int w,int wt)
{
    e[tot].w=w;e[tot].wt=wt;
    e[tot].next=start[v];start[v]=tot++;
}

void spfa(int s)
{
    int i,v,N=0;
    deque<int> dq;
    for(v=0;v<n;v++) d[v]=inf;
    d[s]=0;
    dq.push_back(s);dq.push_back(n);
    while(!dq.empty())
    {
        v=dq.front();dq.pop_front();
        if(v==n)
        {if(N++>n) return;dq.push_back(n);}
        else
            for(i=start[v];i!=-1;i=e[i].next)
            {
                if(d[e[i].w]>d[v]+e[i].wt)
                {
                    d[e[i].w]=d[v]+e[i].wt;
                    dq.push_back(e[i].w);
                }
            }
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int m,i,a,b,c,maxnum=0;
    scanf("%d",&m);
    tot=0;for(i=0;i<maxn;i++) start[i]=-1;
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(b+1,a,-c);
        if(b+1>maxnum) maxnum=b+1;
    }
    for(i=0;i<maxnum;i++)
    {
        add(i,i+1,1);
        add(i+1,i,0);
    }
    n=maxnum+1;
    spfa(maxnum);
    printf("%d",d[maxnum]-d[0]);
    return 0;
}