分析

• 这一题是一定有解的，因为最坏的情况下我们可以把1~50000中的数据全部选上。

• 本次存在两种做法：（1）贪心；（2）差分约束。下面使用差分约束解决这个问题。

• 这里可以使用前缀和的思想求解，因为前缀和中S[0]=0，所有这里将$a_i,b_i$所在的区间范围加上一个1，区间范围变成了[1, 50001]，这样并不影响最终的结果。

• S[i]表示：1~i中被选出数的个数。我们最终要求解的就是$S_{50001}$的最小值，因此需要使用最长路径。

• 对于S，S需要满足如下条件：

（1）$S_i \ge S_{i-1}, 1 \le i \le 50001$；

（2）$S_i - S_{i-1} \le 1 \iff S_{i-1} \ge S_i - 1$；

（3）区间[a, b]中至少有c个数$\iff S_b - S_{a - 1} \ge c \iff S_b \ge S_{a-1} + c$；

• 需要验证一下：从源点出发，是否一定可以走到所有的边。根据条件（1），从i-1可以走到i，因此从0可以走到1，从1可以走到2，......，因此存在这样的源点。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 50010, M = 150010;

int n;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int q[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa() {

    memset(dist, -0x3f, sizeof dist);

    int hh = 0, tt = 0;
    q[tt++] = 0;
    st[0] = true;
    dist[0] = 0;

    while (hh != tt) {

        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

int main() {

    scanf("%d", &n);

    memset(h, -1, sizeof h);

    for (int i = 1; i <= 50001; i++) {
        add(i - 1, i, 0);
        add(i, i - 1, -1);
    }

    for (int i = 0; i < n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a++, b++;
        add(a - 1, b, c);
    }

    spfa();

    printf("%d\n", dist[50001]);

    return 0;
}