$a_i$和$b_i$确定了点的数量,不希望使用$s_0$因此整体加1,n的数量确定了边数
1.确定不等关系,本题需要借助一个额外的概念前缀和,用$s_i$表示1~i中选择的数的个数,为满足前缀和定义,需要让$a_i$和$b_i$加1,此时$s_i\in[1,50001]$,$s_0=0$,符合定义。对于定义的$s_i$,满足$$s_i>=s_i-1$$ $$s_i-s_{i-1}<=1$$ $$s_b-s_a>=c$$
2.确定源点可以走到所有边,$s_0$为起点,满足$s_0<=s_1<=s_2…$,因此$s_0$可以遍历所有边
#include<iostream>
#include<cstring>
using namespace std;
const int N=50010,M=150010;
int h[N],e[M],ne[M],w[M],idx;
int dist[N],n,q[N];
bool st[N];
void add(int a,int b,int c){
w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void spfa(){
memset(dist,-0x3f,sizeof dist);
int tt=1,hh=0;
st[0]=true;
dist[0]=0;
q[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]){
st[j]=true;
q[tt++]=j;
if(tt==N) tt=0;
}
}
}
}
}
int main(){
//额外设置一个s 表示1到s中选择的数的数量 最终结果是s50001,需要提前将ai,bi加1 将0空出来
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=50001;i++){
//si>=si-1
add(i-1,i,0);
//si-si-1<=1 si-1>=si-1
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++;
//区间[a,b]至少有c个数,sb-sa>=c sb>=sa+c
add(a-1,b,c);
}
spfa();
cout<<dist[50001];
return 0;
}