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

• 2018-01-05
• 0
• 0

## Problem:

 Time Limit: 2000MS Memory Limit: 65536K

Description

You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that:
reads the number of intervals, their end points and integers c1, ..., cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
writes the answer to the standard output.

Input

The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

Output

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.

Sample Input

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

Sample Output

`6`

Source

Southwestern Europe 2002

## Solution:

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

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

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

## 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);
// 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;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai