# POJ 1716 Integer Intervals 【差分约束】

xiaoxiao2021-03-01  54

Integer Intervals

Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 15647 Accepted: 6631

Description

An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.  Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.

Input

The first line of the input contains the number of intervals n, 1 <= n <= 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.

Output

Output the minimal number of elements in a set containing at least two different integers from each interval.

Sample Input

4 3 6 2 4 0 2 4 7

Sample Output

### 4建图不要用vector，这道题会T；

#include<cstdio> #include<queue> #include<vector> #include<cstring> using namespace std; const int MAX = 100007; const int INF = 0x3f3f3f3f; struct node{ int to, c, next; node() {} node(int to, int c, int next) : to(to), c(c), next(next) {} }e[MAX]; int head[MAX]; int dis[MAX], vis[MAX]; queue <int> q; int cnt = 0; void add(int x, int y, int z){ e[cnt] = {y, z, head[x]}; head[x] = cnt++; } int mn, mx; int spfa() { fill(dis + mn + 1, dis + mx + 1, -INF); vis[mn] = 1; q.push(mn); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i = head[u]; i != -1; i = e[i].next) { int to = e[i].to; int c = e[i].c; if(dis[to] < dis[u] +c) { dis[to] = dis[u] + c; if(!vis[to]) { q.push(to); vis[to] = 1; } } } } return dis[mx]; } int main(){ int n; scanf("%d", &n); memset(head, -1, sizeof head); mx = -INF, mn = INF; for(int i = 0, x, y; i < n; i++){ scanf("%d%d", &x, &y); y++; add(x, y, 2); mn = min(x, mn), mx = max(mx, y); } for(int i = mn; i <= mx; i++){ add(i, i + 1, 0); add(i + 1, i, -1); } printf("%d\n", spfa()); return 0; }