区间选点Plus

问题描述

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

Output: 
6

Limitation

Time limit		2000 ms
Memory limit	65536 kb

解题思路

差分约束

差分约束系统中的每个约束条件$x_i - x_j ≤ c_k$都可变形成$x_i ≤ x_j + c_k$，这与单源最短路中的不等式dis[u] ≤ dis[v] + w非常相似。因此可以把 x_i 看作图中的节点，$x_i - x_j ≤ c_k$表示从节点 i 到节点 j 的一条权值为c_k的有向边。

设dis[0] = 0并向每一个点连一条边，跑单源最短路，若图中存在负环，则给定的差分约束系统无解，否则， x_i = dis[i]为该差分约束系统的一组解。

求存在负边的单源最短路可以用SPFA。

本题解法

用一个前缀和sum[i]表示区间[begin, i]之内选取的点的个数，则sum[b] - sum[a] ≥ c表示区间[a, b]内至少选取了c个点，sum[i] - sum[i - 1]表示第 i 个点选或不选，因此可以转化成差分约束的形式。

n 个区间，可以看成 n 个差分约束，由 a_i 到 b_i + 1 的边，权重为 c_i ，加入到图中，但是并不能保证图的联通，因此每一个相邻的点之间要加入有向边(i, i + 1, 0)和(i + 1, i, -1)，即差分约束0 ≤ sum[i + 1] - sum[i] ≤ 1，即表示第 i + 1 个点选/不选(存在/不存在)。

本题求下界，所以SPFA要跑最长路，从所有区间的最左端点跑到最右端点即可。

源代码

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

const int maxN = 1e9;

struct node {
	int ele;
	int w;
	node* next;
	node() { ele = -1; w = -2; next = NULL; }
	node(int e, int _w) :ele(e), w(_w) { next = NULL; }
};

class linkedList {
private:
	node* header;
	int size;
public:
	linkedList() { header = NULL; size = 0; }
	~linkedList() { clear(); }
	int getSize() { return size; }
	node* getHeader() { return header; }
	void add(int ele, int w) {
		node* p = new node(ele, w);
		if (header == NULL)
			header = p;
		else {
			node* temp = header;
			node* temp2 = NULL;
			while (temp != NULL) {
				temp2 = temp;
				temp = temp->next;
			}
			temp2->next = p;
		}
		size++;
	}
	void clear() {
		node* temp = header;
		node* ttemp = NULL;
		while (temp != NULL) {
			ttemp = temp;
			temp = temp->next;
			ttemp = NULL;
		}
		header = NULL;
		delete temp;
		delete ttemp;
		delete header;
		size = 0;
	}
};

const int maxSize = 50050;

class graph {
private:
	linkedList arr[maxSize];
	int dis[maxSize];
	int vis[maxSize];
	int dots;
	int size;
public:
	graph() { 
		dots = 0;
		size = 0;
		memset(dis, -maxN, maxSize);
		memset(vis, 0, maxSize);
	}
	graph(int n) { 
		dots = n;
		size = 0;
		memset(dis, -maxN, maxSize);
		memset(vis, 0, maxSize);
	}
	~graph() {  }
	void add(int u, int v, int w) {
		arr[u].add(v, w);
		size++;
	}
	int spfa(int s, int e) {
		for (int i = 0; i <= dots; i++) {
			dis[i] = -maxN;
			vis[i] = 0;
		}
		dis[s] = 0;
		vis[s] = 1;
		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			vis[x] = 0;
			for (node* p = arr[x].getHeader(); p != NULL; p = p->next) {
				int w = p->w;
				int v = p->ele;
				if (dis[v] < dis[x] + w) {
					dis[v] = dis[x] + w;
					if (!vis[v]) {
						q.push(v);
						vis[v] = 1;
					}
				}
			}
		}
		return dis[e];
	}
};


int main() {
	int n;
	scanf_s("%d", &n);
	graph G(n);

	int left = maxN, right = -1;
	while (n--) {
		int a, b, c;
		scanf_s("%d %d %d", &a, &b, &c);
		G.add(a, b + 1, c);
		left = min(left, a);
		right = max(right, b + 1);
	}
	for (int i = left; i <= right; i++) {
		G.add(i + 1, i, -1);
		G.add(i, i + 1, 0);
	}
	
	int ans = G.spfa(left, right);
	printf("%d\n", ans);

	return 0;
}