d[i]表示在[0,i]这个区间内一共选了d[i]个数
对于每个为[ai,bi]的区间，你必须在这个区间上至少取ci个不同的整数，用d[i]如何表示？
d[ bi ]-d[ ai-1 ] >= ci
Edge:(ai-1 -> bi) val = ci
另外：
0<=d[i]-d[i-1]<=1
对应边Edge:(i-1,i) val=0 Edge(i,i-1) val=-1
可以令d[maxa-1]=0
那么，最后d[maxb]-d[maxa-1] 就是最后的答案。
#include <cstdio>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 200001
int first[N],e,d[N], w[N],v[N],next[N];
int n,m;
bool inq[N];
void init(){
e=0;
memset(first,-1,sizeof(first));
memset(inq,0,sizeof(inq));
}
void addedge(int a,int b,int x){
v[e]=b;
next[e]=first[a];
w[e]=x;
first[a]=e++;
}
void SPFA(int min1,int max1){
for(int i=min1+1;i<=max1;i++){
d[i]=-INF;
}
d[min1]=0;
queue<int> q;
q.push(min1);
inq[min1] = 1;
while(!q.empty()){
int ith = q.front();
q.pop();
inq[ith] = 0;
for(int i = first[ith];i != -1;i = next[i]){
if(d[v[i]]<d[ith]+w[i]){
d[v[i]] = d[ith]+w[i];
if(!inq[v[i]]){
q.push(v[i]);
inq[v[i]] = 1;
}
}
}
}
}
int main(){
// freopen("test.txt","r",stdin);
int t,a,b,x;
scanf("%d",&t);
init();
int s=1<<30,e=0;
for(int i=0;i<t;i++){
scanf("%d%d%d",&a,&b,&x);
addedge(a-1,b,x);
if(a-1<s)s=a-1;
if(b>e)e=b;
}
for(int i=s;i<e;i++){
addedge(i,i+1,0);
addedge(i+1,i,-1);
}
SPFA(s,e);
printf("%d
",d[e]);
return 0;
}