差分约束经典题。设s[i]为前缀和，则有
s[i]-s[i-1]<=1 （i往i-1连-1的边）
s[i]>=s[i-1] （i-1往i连0的边）
s[b]-s[a-1]>=c （a-1往b连c的边）
最小值就改>=然后跑最长路
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #define ll long long using namespace std; const int maxn=500010,inf=1e9; struct poi{int too,pre,sum;}e[maxn]; int n,m,x,y,z,front,rear,tot,mx,mn; ll dist[maxn],ans; int h[maxn],v[maxn],last[maxn],tim[maxn]; bool flag; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;} void spfa() { for(int i=mn;i<=mx;i++)v[i]=0,dist[i]=-inf; dist[mn]=0;v[mn]=1;front=rear=0;h[++rear]=mn; while(front!=rear) { int now=h[++front];if(front==maxn)front=-1; for(int i=last[now],too=e[i].too;i;i=e[i].pre,too=e[i].too) if(dist[too]<dist[now]+e[i].sum) { dist[too]=dist[now]+e[i].sum; if(++tim[too]>233){printf("-1");flag=1;return;} if(!v[too]) { v[too]=1;h[++rear]=too; if(rear==maxn)rear=-1; } } v[now]=0; } } int main() { while(~scanf("%d",&n)) { memset(last,0,sizeof(last)); memset(dist,0,sizeof(dist)); flag=0;mx=-inf;mn=inf; for(int i=1;i<=n;i++) { read(x);read(y);read(z); mx=max(mx,y);mn=min(mn,x); add(x-1,y,z); } mn--; for(int i=mn;i<mx;i++)add(i,i+1,0),add(i+1,i,-1); spfa(); if(flag)continue; printf("%lld ",dist[mx]); } return 0; }