[POJ 1201] Intervals【差分约束系统】

• 2018-01-05
• 0
• 0

Problem:

Description

Input

Output

Sample Input

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

Sample Output

6

Source

Solution:

这题是差分约束系统的经典题。

我们用 S[i] 表示前缀和，即 [1, i] 中有几个整数属于 Z 集合。

于是读入的数据“在 [a, b] 中至少有 c 个整数属于 Z 集合”可以转化为

• S[b] - S[a - 1] ≥ c，可以化为三角不等式如下：
• S[b] ≥ S[a - 1] + c …… i)

而根据题目的隐含条件，每个整数要么不在集合 Z 中，要么只在集合中出现一次，即

• 0 ≤ S[i + 1] - S[i] ≤ 1，可以化为三角不等式如下：
• S[i + 1] ≥ S[i] …… ii)
• S[i] ≥ S[i + 1] - 1 …… iii)

联立 i), ii), iii) 得到差分约束系统。

【差分约束系统的最短/长路求解】

我们可以发现，最短/长路的求解算法的核心松弛操作 (Relax) 就是建立在三角不等式的基础上。所以我们可以通过最短/长路来求解差分约束系统的最值。

求最小值，则将不等式化为 x ≥ y + C 的形式，从 y -> x 连权值为 C 的边，跑最长路即可。

求最大值，则将不等式化为 x ≤ y + C 的形式，从 y -> x 连权值为 C 的边，跑最短路即可。

Code: O(kN) [2476K, 235MS]

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

int n, L = 0x3f3f3f3f, R = 0;

struct Edge{
	int np, val;
	Edge *nxt;
};

struct Graph{
	Edge *V[50005], E[150005];
	int tope;
	
	inline void addedge(int u, int v, int w){
		E[++tope].np = v + 1, E[tope].val = w;
		E[tope].nxt = V[u + 1], V[u + 1] = &E[tope];
	}  // Shift subscriptions rightwards to avoid overflowing
} G;

queue<int> q;
bool inq[50005];
int dis[50005];

inline void SPFA_Longest_Path(int S){
	memset(dis, -1, sizeof(dis)), dis[S] = 0;
	q.push(S), inq[S] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop(), inq[u] = 0;
		for(register Edge *ne = G.V[u]; ne; ne = ne->nxt)
			if(dis[u] + ne->val > dis[ne->np]){  // Find the longest path
				dis[ne->np] = dis[u] + ne->val;
				if(!inq[ne->np]) q.push(ne->np), inq[ne->np] = 1;
			}
	}
}

int main(){
	scanf("%d", &n);
	for(register int i = 1; i <= n; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		G.addedge(a - 1, b, c);
		// S[b] - S[a - 1] >= c  ==>  S[b] >= S[a - 1] + c
		L = min(L, a - 1), R = max(R, b);
	}
	for(register int i = L; i < R; i++) G.addedge(i, i + 1, 0), G.addedge(i + 1, i, -1);
	// 0 <= S[i + 1] - S[i] <= 1  ==>  S[i + 1] >= S[i] && S[i] >= S[i + 1] - 1
	L++, R++;  // Shift subscriptions rightwards to avoid overflowing
	SPFA_Longest_Path(L);
	printf("%d\n", dis[R]);  // dis[] is exactly the S[] which stands for the prefix sum of the numbers in Z
	return 0;
}