题解：P8240 [AGM 2022 资格赛] 偷铀计划

· · 题解

Kruskal 重构树板子。

首先我们把这 k 个守卫进行一遍最短路，求得每个点距离最近的守卫的距离 dis_i。

由于有 k 个守卫，所以我们跑一遍多源 dijkstra 即可。

这样一条边 (u ,v) 的边权就转化为了 \min\left(dis_u ,dis_v\right)，我们要求的就是 S 到 T 的所有路径中最小的边权值的最大值。

这个问题很像 Kruskal 重构树板子，我们跑最大生成树然后直接做 Kruskal 重构树即可。

但是注意答案是大于 x 而不算等于，因此如果答案非 0 需要减一。

总结这题是两个板子相加，但是我还是调了好久。。。

# include <bits/stdc++.h>

# define int long long
# define up(i, x, y) for (int i = x; i <= y; i++)
# define dn(i, x, y) for (int i = x; i >= y; i--)
# define inf 1e18

using namespace std;

inline int read(){int x = 0, f = 0;char ch = getchar();while (!isdigit(ch)) {f |= (ch == '-');ch = getchar();}while (isdigit(ch))x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();return f ? -x : x;}
inline void write(int x){if (x < 0)putchar('-'), x = -x;if (x > 9)write(x / 10);putchar(x % 10 | 48);}
inline void writeln(int x){write(x), putchar('\n');}
inline void writesp(int x){write(x), putchar(' ');}

const int N = 2e5 + 10 , M = 2e5 + 10;
int n ,m ,fa[N] ,val[N] ,dep[N] ,lg[N] ,st[N] ,ed[N] ,dis[N] ,Fa[N][21];
bool vis[N];
priority_queue < pair <int ,int> ,vector < pair <int ,int> > ,greater < pair <int ,int> > > pq;
namespace lolcrying {    
    struct node {int st ,ed ,w;} tree[N << 1];
    struct EDGE {int to ,w ,nxt;}graph[M << 1];
    struct EDGE1 {int to ,nxt;} edge[N << 1];
    int cnt ,cnt1 ,head[N] ,head1[N];
    inline void add(int u ,int v ,int w) {
        graph[++ cnt] = {v ,w ,head[u]} ,head[u] = cnt;
    } inline void add1(int u ,int v) {
        edge[++ cnt1] = {v ,head1[u]} ,head1[u] = cnt1;
    }
/*上面建边。*/

    inline int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
    inline bool cmp(node x ,node y) {return x.w > y.w;}
/*倍增求 LCA。*/

    # define fa Fa 
    inline void dfs (int u ,int fath){
        fa[u][0] = fath ,dep[u] = dep[fath] + 1 ,vis[u] = 1;
        up (i ,1 ,20) fa[u][i] = fa[fa[u][i - 1]][i - 1];
        for (int i = head1[u] ; i ; i = edge[i].nxt) {
            int v = edge[i].to;
            if (v == fath) continue;
            dfs (v ,u);
        }
    } inline int LCA (int u ,int v) {
        if (dep[u] < dep[v]) swap (u ,v);
        while (dep[u] ^ dep[v]) u = fa[u][lg[dep[u] - dep[v]]];
        if (u == v) return u;
        dn (i ,20 ,0) if (fa[u][i] ^ fa[v][i]) u = fa[u][i] ,v = fa[v][i];
        return fa[u][0];
    }
    # undef fa

    signed main () {
        n = read() ,m = read();
        up(i ,1 ,m) {
            int u = read() ,v = read() ,w = read();
            st[i] = u ,ed[i] = v;
            add(u ,v ,w) ,add(v ,u ,w);
        }
        int k = read();

/* 跑多源 dijkstra。*/
        up(i ,1 ,n) dis[i] = inf;

        up(i ,1 ,k) {
            int x = read();
            dis[x] = 0;
            // cout << x << " is : " << x << endl;
            pq.push({dis[x] ,x});
        }

        while(!pq.empty()) {
            int u = pq.top().second;
            pq.pop();
            if(vis[u]) continue;
            vis[u] = 1;
            for(int i = head[u] ; i ; i = graph[i].nxt) {
                int v = graph[i].to ,w = graph[i].w;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    pq.push ({dis[v] ,v});
                }
            }
        }
        // up (i ,1 ,n) writeln (dis[i]);
        up (i ,1 ,m) tree[i] = {st[i] ,ed[i] ,min(dis[st[i]] ,dis[ed[i]])};
//按照边权跑最大生成树，并建立 Kruskal 重构树。*/

        sort(tree + 1 ,tree + 1 + m ,cmp);
        up (i ,1 ,n) fa[i] = i;
        int idx = n;
        up (i ,1 ,m) {
            int u = tree[i].st ,v = tree[i].ed ,w = tree[i].w;
            int fax = find(u) ,fay = find(v);
            if (fax ^ fay) {
                val[++ idx] = w;
                fa[fax] = fa[fay] = fa[idx] = idx;
                add1(idx ,fax) ,add1(idx ,fay);
                add1(fax ,idx) ,add1(fay ,idx);
            }
        } n = idx;
        lg[0] = -1;
        up (i ,1 ,n) vis[i] = 0 ,lg[i] = lg[i >> 1] + 1;
        int rt = find(1);
        dfs(rt ,0);
        int Q = read();
        while (Q --) {
            int u = read() ,v = read();
//注意 -1！
            writeln (max (0ll ,-1 + val[LCA(u ,v)]));
        }
        return 0;
    }
}
signed main () {
    int T = 1;
    while (T --) lolcrying :: main ();
    return 0;
}