题目描述：

详见题目

http://acm.pku.edu.cn/JudgeOnline/problem?id=1201

自己用汉语说估计比英文还长。

解题报告：

设F(n)为0到n-1这些数在结果Z集合中的个数。

对于自然数x，有0 < = F(x+1) - F(x) <= 1，即F(x+1) - F(x) <= 1 && F(x) - F(x+1) <= 0

对于输入的a b c有F(b + 1) – F(a) >= c，即F(a) – F(b + 1) < = c

如果区间的最大值为max，可知问题的解为F(max+1) – F(0)。

代码如下：
#include<iostream>
using namespace std;
#define size 50004
#define Max 2000000000
int d[size], ecnt, n, lar;
struct edge{int from, to, v;}e[size * 5];
bool bellman()
{
    for(int i = 1; i <= lar; i++) d[i] = Max;
    d[0] = 0;
    for(int i = 1; i <= lar; i++)
    {
        bool flag = false;
        for(int j = 0; j < ecnt; j++)
            if (d[e[j].from] + e[j].v < d[e[j].to])
            {
                d[e[j].to] = d[e[j].from] + e[j].v;
                flag = true;
            }
        if (!flag) return true;
    }
    for(int j = 0; j < ecnt; j++)
        if (d[e[j].from] + e[j].v < d[e[j].to]) return false;
    return true;
}
void insert(int from, int to, int v)
{
    e[ecnt].from = from;e[ecnt].to = to;
    e[ecnt++].v = v;
}
int from, to, c;
int main()
{
    while(scanf("%d", &n) != EOF)
    {
        lar = ecnt = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d%d", &from, &to, &c);
            if (to + 1 > lar) lar = to + 1;
            insert(to + 1, from, -c);
        }
        for(int i = 1; i <= lar; i++)
        {
            insert(0, i, 0);
            insert(i, i + 1, 1);
            insert(i + 1, i, 0);
        }
        ecnt-=2;
        bellman();
        printf("%d\n", d[lar] - d[1]);
    }
    return 0;
}