UPC-5155 - Security Badges - 思维

题目链接：

http://exam.upc.edu.cn/problem.php?id=5155

题目：

题目描述

You are in charge of the security for a large building. The building has a map, consisting of rooms, and doors between the rooms. Each door has a security code, which consists of a range of numbers, specified by a lower bound and an upper bound. Each employee has a uniquely numbered security badge. Only a security badge with a number within a door’s range can go through that door.
Your boss wants a quick check of the security of the building. Given a starting room and a destination room, how many security badge numbers can go from the start to the destination?

输入

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line containing three integers integer n (1 ≤ n ≤ 1,000), m (1 ≤ m ≤ 5,000) and k (1 ≤ k ≤ 109 ), where n is the number of rooms, m is the number of doors, and k is the number of badges. The rooms are numbered 1..n and the badges are numbered 1..k.
The next line will contain two integers, s and d (1 ≤ s,d ≤ n), which indicate the starting room and destination room.
Each of the next m lines will contain four integers, a, b (1 ≤ a,b ≤ n, a≠b), min and max (1 ≤ min ≤ max ≤ k) describing a door, where the door from room a to room b (and not back), and the badges range for the door is min..max, inclusive.

输出

Output a single integer, which is the number of badges that can go from the start room to the destination room.

样例输入

样例输出

题意：

有n个点，m条边，还有一个总上界k，你需要从s点走到t点，对于每条边u v l r，你手中持有的权值需要在[l, r]的范围内才能从u走到v，问有多少种不同的权值可以成功地从s点走到t。

思路：

刚开始想的是让手里的权值也变为一个范围[0, k]，这样从s点走到t点之后剩下的范围就是最终的范围，可是这样无法解决环路的问题，考虑其它做法。对于所有给出上下界，最终的权值所在的范围的端点一定在这些数值里，所以我们把所有的上下界都存在一个边界数组里，排序去重，这样就得到了一个升序数组，数组中的每两个相邻的元素都是可能从起点走到终点的最小范围。

考虑两个相邻的边界$a_i$，$a_{i + 1}$，按照我当时的思路，check()一下$[a_i, a_{i + 1}]$是不是一个可行解，考虑：

3 2 6
1 2 1 4
2 3 3 5

边界数组为：$\{1, 3, 4, 5\}$，所有的最小可能可行区间为：$[1,3]、[3,4]、[4,5]$，分别对其check()之后发现$[3,4]$可以通过，即答案是这个区间的长度：2。

再考虑这个样例：

3 2 6
1 2 1 4
2 3 4 5

边界数组为：$\{1,4,5\}$所有的最小可能可行区间为：$[1,4]、[4,5]$，分别对其check()之后发现都不可以通过，但是发现这个样例应该答案为1，即：4是一个可行解。

可以发现，某个区间无法通过的时候，其端点仍有可能可以独立通过，于是考虑将区间拆开：

将所有的闭区间拆为左端点，右端点，中间的开区间三部分，即：$[a,b]$拆为$[a,a]、(a,b)、[b,b]$，这样就比较完善了。

考虑优化，在我们check()一个点的时候，常规做法是将其置为一个左右区间相等的闭区间，事实上直接check()单点的时候效率更高，那么开区间能不能也转化为单点呢？对于本题来说是可以的。

考虑对于一个区间$(a, b)$，发现只要我们只要check()这个区间内的任意一个点，就能知道这个区间是否可行，下面给出证明：

设有一区间$(a,b)$不能通过check()，但是其中某个独立的点$x$可以通过check()，那么就一定存在一个点x存在于上文提到的边界数组中，且$a \leq x \leq b$，但$a、b$两个点在边界数组中一定是两个相邻的点，矛盾。

实现：

#include <bits/stdc++.h>
const int maxn = 1007, maxm = 5007;
struct Edge {
    int next, to, l, r;
} edge[maxm];
int head_edge[maxn], cnt_edge, n, m, k, S, T, ans, point[maxm << 2], tot;
bool vis[maxn], flag;
void addedge(int u, int v, int l, int r) {
    edge[cnt_edge] = {head_edge[u], v, l, r};
    head_edge[u] = cnt_edge++;
}
bool dfs(int u, int x) {
    if (u == T) return (flag = true);
    for (int i = head_edge[u], v; ~i; i = edge[i].next) {
        v = edge[i].to;
        if (vis[v] || x < edge[i].l || x > edge[i].r) continue;
        vis[v] = true;
        if (dfs(v, x), flag) return true;
    }
}
bool check(int x) {
    memset(vis, 0, sizeof(vis));
    flag = false;
    return dfs(S, x), flag;
}
 
int main() {
//    freopen("in.txt", "r", stdin);
    scanf("%d%d%d%d%d", &n, &m, &k, &S, &T);
    memset(head_edge, 0xff, sizeof(head_edge));
    point[tot++] = 1, point[tot++] = k + 17;
    for (int i = 0, u, v, l, r; i < m; i++) {
        scanf("%d%d%d%d", &u, &v, &l, &r);
        point[tot++] = l, point[tot++] = r;
        addedge(u, v, l, r);
    }
    std::sort(point, point + tot);
    tot = int(std::unique(point, point + tot) - point);
    for (int i = 0; i < tot; i++) {
        if (check(point[i])) ans++;
        if (i + 1 < tot && point[i] + 1 < point[i + 1] && check(point[i] + 1))
            ans += point[i + 1] - point[i] - 1;
    }
    printf("%d\n", ans);
    return 0;
}

UPC-5155 - Security Badges - 思维