算法
差分约束
题目描述
给定一个数轴上的 n 个区间，要求在数轴上选取最少的点使得第 i 个区间 [ai, bi] 里至少有 ci 个点
解题思路
设从前i个节点中选取的节点数为sum[]，则通过题目可知：
- 第 i 个区间 [ai, bi] 里至少有 ci 个点即：sum[bi] - sum[ai-1] >= ci
- sum有意义即：0 <= sum[i] - sum[i-1] <= 1
由于要求最小差分约束，则构造大于等于差分约束式；从而得到以下三个差分约束式： - sum[bi] - sum[ai-1] >= ci
- sum[i] - sum[i-1] >= 0
- sum[i-1] - sum[i] >= 1
根据差分约束式建立相应边即可。
求解差分差分约束式即将SPFA中判断if（d[x]>=d[y]+w）改为相应判断式即可，本题为大于等于式，即：if（!(sum[x]>=w+sum[y])）。
代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int Maxn=50010;
struct At{
int x,y,w,next;
} e[Maxn*4];
int h[Maxn];
int sum[Maxn];
bool in[Maxn];
void SPFA(int st){
memset(sum,0xc0,sizeof(sum));
memset(in,0,sizeof(in));
queue<int> q;
q.push(st);in[st]=1;
sum[st]=0;
while(!q.empty()){
int x=q.front();
q.pop();in[x]=0;
for(int i=h[x];i>0;i=e[i].next){
int y=e[i].y,w=e[i].w;
if(!(sum[y]>=sum[x]+w)){
sum[y]=sum[x]+w;
q.push(y);
in[y]=1;
}
}
}
}
void makeE(int x,int y,int w,int cnt){
x=x+1,y=y+1;
e[cnt].x=x;
e[cnt].y=y;
e[cnt].w=w;
e[cnt].next=h[x];
h[x]=cnt;
}
int main(){
int n;
cin>>n;
int maxb=0;
//int mina=0;
int a,b,c;
int cnt=0;
while(n--){
cin>>a>>b>>c;
makeE(a-1,b,c,++cnt);
maxb=max(maxb,b);
//mina=min(mina,a-1);
}
for(int i=0;i<=maxb;i++){
makeE(i-1,i,0,++cnt);
makeE(i,i-1,-1,++cnt);
}
SPFA(0);
cout<<sum[maxb+1]<<endl;
return 0;
}
题目总结
这一类差分约束的题目即将题目中条件转化为差分约束即可。
注意还需要添加使构造数组有意义的判断式。
D题中仅仅做了数据的强化，注意点从0开始，故而sum[1]应表示0节点，即将整个sum数组进行平移。
题目原文
给定一个数轴上的 n 个区间，要求在数轴上选取最少的点使得第 i 个区间 [ai, bi] 里至少有 ci 个点
使用差分约束系统的解法解决这道题
使用差分约束系统的解法解决这道题
使用差分约束系统的解法解决这道题
使用差分约束系统的解法解决这道题
使用差分约束系统的解法解决这道题
Input
输入第一行一个整数 n 表示区间的个数，接下来的 n 行，每一行两个用空格隔开的整数 a，b 表示区间的左右端点。1 <= n <= 50000， 0 <= ai <= bi <= 50000 并且 1 <= ci <= bi - ai+1。
Output
输出一个整数表示最少选取的点的个数
Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
