POJ1716 Integer Intervals

十月 17, 2020 2543

题意简述

给你一些非负整数区间，现在让你选出一堆非负整数来，满足每个区间里至少有两个不同的整数。输出最少需要选多少个整数。

解题思路

一个经典套路。

令 d_i 表示 [0, i] 这个区间里选了多少数。

题目给定的约束条件转化为，对于区间 [a, b] ，要求满足：

d_b - d_{a - 1} \geq 2

同时，对于 d 也有一个限制，就是对于长度为 1 的非负整数集合 \{a\} ，我们至多能选一个，也即：

0 \leq d_{a} - d_{a - 1} \leq 1

把这两个条件加边跑最长路就 win 了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// Accepted

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 10000 + 10;

struct Edge {
    int v, w; Edge(int _v = 0, int _w = 0) : v(_v), w(_w) {}
};

int n, mn = 0x3f3f3f3f, m;
std::vector<Edge> G[MAXN];

int spfa(int s) {
    static int dist[MAXN]; memset(dist, -1, sizeof dist);
    static bool inq[MAXN]; 
    dist[s] = 0; std::queue<int> q;
    q.push(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = 0, siz = (int) G[u].size(); i < siz; ++i) {
            int v = G[u][i].v, w = G[u][i].w;
            if (dist[v] < dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) inq[v] = true, q.push(v);
            }
        }
    }
    return dist[n];
}

int main() {
    m = read();
    for (int i = 1; i <= m; ++i) {
        // 编号往后移两个
        int a = read() + 2; int b = read() + 2;
        n = std::max(n, std::max(a, b));
        mn = std::min(mn, std::min(a, b));
        G[a - 1].push_back(Edge(b, 2));
        // printf("%d -> %d : %d\n", a - 1, b, 2);
    }
    for (int i = mn; i <= n; ++i) {
        G[i - 1].push_back(Edge(i, 0));
        // printf("%d -> %d : %d\n", i - 1, i, 0);
        G[i].push_back(Edge(i - 1, -1));
        // printf("%d -> %d : %d\n", i, i - 1, -1);
    }
    printf("%d\n", spfa(mn - 1));
    return 0;
}