Week--8 A - 区间选点 II

题目原文

给定一个数轴上的 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

解题思路

由题知到bi的所有点数d[bi]减去到ai的所有点数d[ai]应大于等于ci,即d[bi]-d[ai-1]>=ci;
同时要使d[]有意义，需要0=<d[i]-d[i-1]<=1.
构造大于等于差分约束得：
d[bi]>=d[ai-1]+ci
d[i]>=d[i-1]
d[i-1]>=d[i]+(-1)
根据差分约束式建边，利用SPFA（判断条件改为if(!(d[x]>=d[y]+w))）求解即可。

实现代码

#include<iostream>
#include<cstdio> 
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 50010;
const int maxm = 150010;
struct Edge {
    int x, y, w, next;
    Edge() {
        x = y = w = next = 0;
    }
    Edge(int x, int y, int w, int cnt) {
        this->x = x;
        this->y = y;
        this->w = w;
        this->next = cnt;
    }
};
Edge e[maxm];
int h[maxn];
int d[maxn];
bool in[maxn];
//插入单项边 
void makeE(int x, int y, int w, int cnt) {
    e[cnt] = Edge(x, y, w, h[x]);
    h[x] = cnt;
}
void search(int st) {//SPFA
    memset(in, 0, sizeof(in));
    queue<int>q;
    //push三件套
    d[st] = 0;
    q.push(st);
    in[st] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        in[x] = 0;

        for (int i = h[x]; i; i = e[i].next)
        {
            int y = e[i].y, w = e[i].w;
            
            if (!(d[y] >=w + d[x]))
            {
                d[y] = w + d[x];
                if (!in[y])
                {
                    q.push(y);
                    in[y] = 1;
                }
            }
        
        }
    }
}

int main() {
    
    int n;
    cin >> n;

    int cnt = 0;
    int x, y, w, next, end = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d", &x, &y, &w);
        makeE(x, y+1, w, ++cnt);
        //st = min(st, x);
        end = max(end, y+1);
    }
        //初始化d
    for (int i = 0; i <=end; i++)
    {
        d[i] = -1e10;
    }
    for(int i=1;i<=end;i++)
    {
        makeE(i-1,i,0,++cnt);
        makeE(i,i-1,-1,++cnt);
    }
    search(0);//0，注意从0开始

    cout << d[end] << endl;
    //system("pause");
    return 0;
}

小结

在建边时需要注意先将端点bi进行平移(bi+1)，因为需要计算bi-(ai-1)，而题中所给范围为0 <= ai <= bi <= 50000，包括0端点。