题意:有\(n(n<=50000)\)个区间，在区间\([a_i,b_i](0<=a_i,b_i<=50000)\)中至少取任意互不相同的\(c_i\)个整数.求在满足n个区间的情况下，至少要取多少个正整数?
分析:差分约束.设\(s[k]\)表示0到k之间最少选出多少个整数.则对于每个区间的限制条件可以看成是\(s[b_i]-s[a_i-1]>=c_i\),这样就是差分约束的模型了,我们在\(a_i-1,b_i\)之间连一条长度为\(c_i\)的有向边(实际代码中我连得是\(a_i,b_i+1\),一个意思.)
然后结合\(s\)数组的定义,\(s[k]-s[k-1]>=0\),所以\(k-1,k\)之间连一条长度为0的有向边,\(s[k]-s[k-1]<=1\)可以看做\(s[k-1]-s[k]>=-1\),所以\(k,k-1\)之间连一条长度为-1的有向边.
建图之后,就可以跑最长路了.题目保证\(1<=c_i<=b_i-a_i+1\),所以不会出现正环.
最长路的起点就是\(min_{a_i}\),终点就是\(max_{b_i}.\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=200005;
int n,minn,maxn,dis[N],visit[N];
int tot,head[N],nxt[N],to[N],w[N];
inline void add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
queue<int>q;
inline void spfa(){
for(int i=minn;i<=maxn;++i)dis[i]=-1e9;//最长路,所以赋值无穷小
q.push(minn);dis[minn]=0;visit[minn]=1;
while(q.size()){
int u=q.front();q.pop();visit[u]=0;
for(int i=head[u];i!=-1;i=nxt[i]){
int v=to[i];
if(dis[v]<dis[u]+w[i]){//注意是最长路
dis[v]=dis[u]+w[i];
if(!visit[v]){
visit[v]=1;
q.push(v);
}
}
}
}
}
int main(){
int T=read();
while(T--){
tot=0;memset(head,-1,sizeof(head));//多组数据初始化,因为有可能起点是0号点,所以head设为-1
minn=1e9,maxn=-1e9;n=read();
for(int i=1;i<=n;++i){
int a=read(),b=read(),c=read();
add(a,b+1,c);
minn=min(minn,a);//编号最小是起点
maxn=max(maxn,b+1);//编号最大是终点
}
for(int i=minn;i<maxn;++i){
add(i,i+1,0);add(i+1,i,-1);
}
spfa();
printf("%d\n",dis[maxn]);
if(T)puts("");
}
return 0;
}