UVA1723 Intervals 题解

· · 题解

题解索引

  1. 题目大意
  2. Solution
  3. AC code
  4. 类似题型

代码类型： C++（cpp）

是否吸氧：否

不压行代码长度：59

题目大意

题面： <传送门>

题意：选数。给出 n 个条件，每次给出 a_i 、 b_i 、 c_i ，表示整数区间 [a_i,b_i] 中至少选 c_i 个数。求满足 n 个条件时，最少需选的区间数。

术语理解： 差分约束 加强题。

Solution

本题并不难，主要在于思路的转化。

我们要使 [a_i,b_i] 的区间里选 c_i 个数，要使满足 n 个条件时选的数最少，那就需要有一些数被多个条件选上。而题目让我们求的并不是哪些数被选，而是被选数的总数。

我们可以这样想：

  1. 设区间最左端点为 x 。

  2. 将问题转化：设 [x,a_i-1] 区间内选了 w_i 个数，设 [x,b_i] 区间内选了 w_i+c_i （因为区间 [a_i,b_i] 之间要求选 c_i 个数）。

  3. 转化为差分约束：区间 [x,b_i] 比区间 [x,a_i-1] 多选了 c_i 个数，即：

设 e_i 表示区间 [x,i] （ x 为总选数区间左端点）选的数的总数。

e_{b_i}-e_{a_i-1}=c_i

即为：

e_{b_i}-e_{a_i-1}\le c_i

那么我们就可以按照差分约束的形式来做了，不过有几个注意事项：

  1. 题目中说过： 0\le a_i\le b_i\le 50000 所以，我们如果建边时选择用 a_i-1 当左端点会出界，所以我们选择将整个区间都右移一格，即 a_i 和 b_i 都 +1 。

  2. 由于区间之间可能不连通，所以我们要建立虚拟源点（超级源点），连所有可能放数字的区间，权值为 0 。

  3. 题目多组数据，记得清数组。

  4. 题目要求非最后一组数据时输出要额外带个空行，所以要在循环时判断一下。

AC code

#include<iostream>
#include<cmath>
#include<cstdio>
#include<queue> 
#include<cstring>
using namespace std;
const int MAXN=1e6+9;
struct Edge{
    int nxt,to,w;
}edge[MAXN];
int t,n;
int maxn=-1,dis[MAXN];
bool vis[MAXN];
int num_edge=0,head[MAXN];
void add_edge(int from,int to,int w){
    edge[++num_edge]=(Edge){head[from],to,w};
    head[from]=num_edge;
}void spfa(int s){
    queue<int>q;
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=edge[i].nxt){
            int to=edge[i].to;
            if(dis[to]<dis[x]+edge[i].w){
                dis[to]=dis[x]+edge[i].w;
                if(!vis[to])q.push(to),vis[to]=1;
            }
        }
    }
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        num_edge=0;
        maxn=-1;
        memset(head,0,sizeof(head));
        for(int i=1;i<=n;i++){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            add_edge(a,b+1,c);
            maxn=max(maxn,b+1);
        }memset(dis,-1,sizeof(dis));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=maxn;i++)dis[i]=-2147483647,vis[i]=0;
        for(int i=1;i<=maxn;i++){
            add_edge(i,i-1,-1);
            add_edge(i-1,i,0);
        }spfa(0);
        printf("%d\n",dis[maxn]);
        if(t)printf("\n");
    }
    return 0;
}

AC记录<传送门>

类似题型

P3275 [SCOI2011]糖果

（差分约束）