DDOSvoid's Blog

bzoj 4144 [AMPPZ2014]Petrol

发表于 更新于 分类于
本文字数： 3.3k 阅读时长 ≈ 3 分钟

题目描述

题目背景

无

题目描述

给定⼀个 n 个点， m 条边的带权⽆向图， 其中有 s 个点是加油 站。 每辆车都有⼀个油量上限 b ， 即每次⾏⾛距离不能超过 b ， 但在加油站可 以补满。 q 次询问， 每次给出 x, y, b ， 表示出发点是 x ， 终点是 y ， 油 量上限为 b ， 且保证 x 点和 y 点都是加油站， 请回答能否从 x ⾛到 y 。 • n,m,s,q≤ 2×10)

输入输出格式

输入格式：

第一行包含三个正整数n,s,m(2<=s<=n<=200000,1<=m<=200000)，表示点数、加油站数和边数。 第二行包含s个互不相同的正整数c[1],c[2],…c[s]，表示每个加油站。 接下来m行，每行三个正整数u[i],v[i],d[i]，表示u[i]和v[i]之间有一条长度为d[i]的双向边。 接下来一行包含一个正整数q(1<=q<=200000)，表示询问数。 接下来q行，每行包含三个正整数x[i],y[i],bi，表示一个询问。

输出格式：

输出q行。第i行输出第i个询问的答案，如果可行，则输出TAK，否则输出NIE。

输入输出样例

输入样例#1：
6 4 5
1 5 2 6
1 3 1
2 3 2
3 4 3
4 5 5
6 4 5
4
1 2 4
2 6 9
1 5 9
6 5 8

输出样例#1：
TAK
TAK
TAK
NIE

简要题意：给定⼀个 $n$ 个点， $m$ 条边的带权⽆向图， 其中有 $s$ 个点是加油站。 每辆车都有⼀个油量上限 $b$ ， 即每次⾏⾛距离不能超过 $b$ ， 但在加油站可以补满。 $q$ 次询问， 每次给出 $x$，$y$，$b$ ， 表示出发点是 $x$ ， 终点是 $y$ ， 油量上限为 $b$ ， 且保证 $x$ 点和 $y$ 点都是加油站， 请回答能否从 $x$ ⾛到 $y$

$n,m,q\le 2\times 10^5$

Solution

我们考虑用将所关键点都扔进 $dijkstra$ 的优先队列里，然后求出离每个非关键点最近的关键点

然后将连接两个属于不同关键点的非关键的边拿出来跑 $kruskal$ 即可

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#define maxn 200010
#define maxm 200010
#define INF 1000000000
#define maxq 200010
using namespace std;

int n, m, k, q, a[maxn];

struct Edge {
    int fr, to, next, w;
} e[maxm * 2]; int c1, head[maxn];
inline void add_edge(int u, int v, int w) {
    e[c1].fr = u; e[c1].to = v; e[c1].w = w;
    e[c1].next = head[u]; head[u] = c1++;
}

struct Queue {
    int k, d;

    friend bool operator < (const Queue &u, const Queue &v) { return u.d > v.d; }
}; 

int dis[maxn], bl[maxn]; bool vis[maxn];
void dijkstra() {
    for (int i = 1; i <= n; ++i) dis[i] = INF;
    for (int i = 1; i <= n; ++i) vis[i] = 0; 
    for (int i = 1; i <= k; ++i) dis[a[i]] = 0, bl[a[i]] = a[i]; 
    priority_queue<Queue> Q;
    for (int i = 1; i <= k; ++i) Q.push({ a[i], 0 });
    while (!Q.empty()) {
        int u = Q.top().k; Q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                bl[v] = bl[u];
                Q.push({ v, dis[v] }); 
            }
        }
    }
}

struct node {
    int u, v, w;

    friend bool operator < (const node &u, const node &v) { return u.w < v.w; } 
} E[maxm]; int c2; 

struct Query {
    int x, y, d, id;

    friend bool operator < (const Query &u, const Query &v) { return u.d < v.d; } 
} Q[maxq]; int ans[maxq];

int fa[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

inline void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return ;
    fa[fx] = fy;
} 

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k >> m;
    for (int i = 1; i <= k; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        add_edge(x, y, z); add_edge(y, x, z);
    } dijkstra();
    for (int i = 0; i < c1; i += 2) {
        int u = e[i].fr, v = e[i].to, w = e[i].w;
        if (bl[u] != bl[v]) E[++c2] = { bl[u], bl[v], dis[u] + dis[v] + w }; 
    } init_fa(n); cin >> q;
    for (int i = 1; i <= q; ++i) cin >> Q[i].x >> Q[i].y >> Q[i].d, Q[i].id = i;
    sort(Q + 1, Q + q + 1); sort(E + 1, E + c2 + 1); 
    for (int i = 1, j = 0; i <= q; ++i) {
        while (j < c2 && E[j + 1].w <= Q[i].d) ++j, merge(E[j].u, E[j].v);
        ans[Q[i].id] = find(Q[i].x) == find(Q[i].y); 
    }
    for (int i = 1; i <= q; ++i) cout << (ans[i] ? "TAK" : "NIE") << "\n"; 
    return 0;
}