(未完待续)简单的差分约束系统入门题目。
题目链接:POJ 1201/TYVJ 1415(Joyoi 3230)/LibreOJ 10087/信息学奥赛一本通 T1509/Southwestern Europe 2002。
题目
题目描述
给定 $n$ 个闭区间 $[a _ i,b _ i]$ 和 $c _ i$ 个整数。你需要构造一个整数集合 $\mathbb{Z}$,使得对于任意 $i\in[1,n]$,$\mathbb{Z}$ 中满足$a _ i\leq x\leq b _ i$ 的整数 $x$ 不少于 $c _ i$ 个,求这样的整数集合 $\mathbb{Z}$ 最少包含多少个数。
简而言之就是,从 $0\to 5\times 10^4$ 中选出尽量少的整数,使每个区间 $[a _ i,b _ i]$ 内都有至少 $c _ i$ 个数被选出。
数据范围
对于全部数据,$1\leq n\leq 5\times 10^4,0\leq a _ i\leq b _ i\leq 5\times 10^4,1\leq c _ i\leq b _ i−a _ i+1$。
题解
思路
很明显,我们可以设 $s _ i$ 表示闭区间 $[0,i]$中共有多少个整数。
那么我们可以轻松得出下面两个结论:
- $0\leq s _ {i+1}-s _ i\leq 1$;
- $s _ {b _ i}-s _ {a _ {i-1}}\geq c _ i$。
想到关于差分约束系统的知识,我们就可以写程序了。
本题的解法采用形如 $X _ i-X _ j\geq v$ 的约束条件,所以是使用SPFA算法求最长路。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
#include<queue>
using std::queue;
#define INF 0X3F3F3F3F
//以上为头文件
const int MAXN=50000+5;//数据范围最大值
bool inque[MAXN];
int n;
int cnt,head[MAXN],to[MAXN*3],w[MAXN*3],Next[MAXN*3];
int dis[MAXN];
queue<int> Q;
void Add_Edge(int,int,int);
bool SPFA(int);
int main(void){
register int i,Min=INF,Max=0;
scanf("%d",&n);
for(i=1;i<=n;++i){
static int a,b,c;
scanf("%d%d%d",&a,&b,&c);
++a,++b;//防止下标出现负数
Add_Edge(a-1,b,c);//注意是a-1
Min=min((int)Min,a-1);
Max=max((int)Max,b);
}
for(i=Min;i<=Max;++i){
Add_Edge(i,i+1,0);
Add_Edge(i+1,i,-1);
}
SPFA(Min);//这里求的是最长路
printf("%d\n",dis[Max]);
return 0;
}
void Add_Edge(int u,int v,int len){
Next[++cnt]=head[u];
to[cnt]=v;
w[cnt]=len;
head[u]=cnt;
return;
}
bool SPFA(int s){
register int i,ID;
memset(inque,false,sizeof(inque));
memset(dis,-0X3F,sizeof(dis));//这里求的是最长路
while(!Q.empty())
Q.pop();
inque[s]=true,dis[s]=0;
Q.push(s);
while(!Q.empty()){
ID=Q.front();
Q.pop();
inque[ID]=false;
for(i=head[ID];i;i=Next[i]){
if(dis[ID]+w[i]>dis[to[i]]){//这里求的是最长路
dis[to[i]]=dis[ID]+w[i];
if(!inque[to[i]]){
inque[to[i]]=true;
Q.push(to[i]);
}
}
}
}
return true;//正常(题目保证有解)
}
近期评论