/* hdu1384–差分约束 求最小个数，构造>=不等式，跑最长路 题目给出的条件不够，需要自己理清楚隐含条件 题目给出的条件： c<=s[b]-s[a-1]<=b-a+1 隐含条件： 0<=s[i+1]-s[i]<=1 */
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int N = 5e4 + 10; const int M = 1e6 + 10; int n; int head[N], tot; int dis[N], cnt[N]; bool vis[N]; int maxx; struct Edge { int to; int w; int nxt; }e[M]; void add(int u, int v,int w) { e[++tot].to = v; e[tot].nxt = head[u]; e[tot].w = w; head[u] = tot; } bool spfa(int s) { for (int i = 0; i <= maxx; i++) { dis[i] = -INF; cnt[i] = 0; vis[i] = 0; } dis[s] = 0; queue<int>q; vis[s] = 1; cnt[s]++; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int v,i = head[u]; i != -1; i = e[i].nxt) { v = e[i].to; if (dis[v] < dis[u] + e[i].w) { dis[v] = dis[u] + e[i].w; if (!vis[v]) { vis[v] = 1; cnt[v]++; if (cnt[v] > maxx)return false; q.push(v); } } } } return true; } int main() { while (scanf("%d", &n) != EOF) { maxx = 0; memset(head, -1, sizeof(head)); tot = 0; for (int a, b, c, i = 1; i <= n; i++) { //题目给出的条件 scanf("%d%d%d", &a, &b, &c); a++; b++; maxx = max(maxx, max(a, b)); add(a - 1, b, c); add(b, a - 1, a - b - 1); } for (int i = 0; i < maxx; i++) { //隐含条件 add(i, i + 1, 0); add(i + 1, i, -1); } spfa(0); printf("%d\n", dis[maxx]); } return 0; }