链接
https://www.acwing.com/problem/content/364/
题目
给定 n 个区间 ([a_i,b_i])和 n 个整数 (c_i)。
你需要构造一个整数集合 Z，使得∀i∈[1,n],Z 中满足(a_i≤x≤b_i)的整数 x 不少于 (c_i) 个。
求这样的整数集合 Z 最少包含多少个数。
输入格式
第一行包含整数 n。
接下来n行，每行包含三个整数(a_i,b_i,c_i)。
输出格式
输出一个整数表示结果。
数据范围
(1≤n≤50000,)
(0≤a_i,b_i≤50000,)
(1≤c_i≤b_i−a_i+1)
输入样例：
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
输出样例：
6
思路
设点(S_i)表示集合中1到i的数的个数，“(a_i≤x≤b_i)的整数x不少于(c_i)个”可以转为为:(S_{b_i}-S_{a_i-1}≥c_i)，以及(S)表示前缀和，有：(S_{i}-S_{i-1}≥0)。由于求集合中的最小元素个数，对应求最小值，那么建一条从(a_i-1)到(b_i)长度为(c_i)的边，以及(i-1)到(i)建一条边权为0的边，spfa跑一遍最长路。最终的答案就是(S_{50000}).
代码
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int h[N],w[N*3],e[N*3],nex[N*3],q[N],dis[N],st[N],idx;
void add(int u,int v,int c){
e[idx]=v;
w[idx]=c;
nex[idx]=h[u];
h[u]=idx++;
}
void spfa(){
memset(dis,-0x3f,sizeof dis);
dis[0]=0;
int hh=0,tt=0;
q[tt++]=0;
st[0]=1;
while(hh!=tt){
int u=q[hh++];
if(hh==N) hh=0;
st[u]=0;
for(int i=h[u];~i;i=nex[i]){
int v=e[i];
if(dis[v]<dis[u]+w[i]){
dis[v]=dis[u]+w[i];
if(!st[v]){
q[tt++]=v;
if(tt==N)tt=0;
st[v]=1;
}
}
}
}
}
int main(){
memset(h,-1,sizeof h);idx=0;
for(int i=1;i<=50001;++i){
add(i-1,i,0);
}
for(int i=1;i<=50001;++i){
add(i,i-1,-1);
}
int n;
cin>>n;
for(int i=1;i<=n;++i){
int a,b,c;
cin>>a>>b>>c;
add(a-1,b,c);
}
spfa();
cout<<dis[50001]<<endl;
return 0;
}