P4768 [NOI2018] 归程 做题记录

听说这是个 Kruskal 重构树的练习题，于是往这方面想。

先预处理出最短路 \(dis\)。

然后建出 Kruskal 重构树（枚举的边按照 \(h\) 从大到小排序）。

然后对于一个询问 \(v,p\)。

\(v\) 不断向上跳，直到海拔 \( 为止，然后这个点的子树内的点都可到达。

于是我们可以找到这个子树内 \(dis\) 最小的点就是答案。

于是这题就做完了。

最短路用 \(\text{Dij}\) 或者 \(\text{SPFA}\)。

Kruskal 重构树用并查集

\(v\) 向上跳用倍增。

子树内 \(dis\) 最小的点可以 ST 表或者线段树。

差不多 10:00 开始写的。

现在是 11:39，我还没调出来，我看看我什么时候调出来。

现在是 14:45，中间睡了两个小时的午觉，我调完了。

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"< b.h; }
}E[MAXN];

struct Node {
    int id, val;
    bool operator < (const Node &b) const { return val > b.val;}
};

struct edge {
    int to, w, nxt;
}e[MAXN << 1];
int head[MAXN], num_edge = 1;

int n, m, Q, K, S, Cnt;
int val[MAXN], fa[MAXN], Log2[MAXN];
int dis[MAXN], Dis[MAXN][21];
int siz[MAXN], dfn[MAXN], fath[MAXN][22], H[MAXN][21];
bool vis[MAXN];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

namespace Cut {
    struct edge { int to, nxt; }e[MAXN << 1];
    int head[MAXN], num_edge = 1;
    int cnt = 0;
    void add_edge(int from, int to) { e[++num_edge] = (edge){to, head[from]}, head[from] = num_edge; }
    void dfs(int u, int fa) {
//        cout< q;
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    q.push((Node){1, 0}), dis[1] = 0;
    while(!q.empty()) {
        int u = q.top().id; q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if(dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if(!vis[v]) q.push((Node){v, dis[v]});
            }
        }
    }
}

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void ExKruskal() {
    sort(E + 1, E + m + 1);
    for(int i = 1; i <= 2 * n; ++i) fa[i] = i;
    for(int i = 1; i <= m; ++i) {
        int u = E[i].fr, v = E[i].to, w = E[i].h;
        int uf = find(u), vf = find(v);
        if(uf != vf) {
            fa[uf] = fa[vf] = ++Cnt;
//            cout<<"edge: "<> 1] + 1;
    while(T--) {
        Clear();
        n = read(), m = read();
        Cnt = n;
        for(int i = 1; i <= m; ++i) {
            E[i].fr = read(), E[i].to = read(), E[i].w = read(), E[i].h = read();
            add_edge(E[i].fr, E[i].to, E[i].w), add_edge(E[i].to, E[i].fr, E[i].w);
        }
        Dij();
        ExKruskal();
        Cut::dfs(Cnt, 0);
        Init();
//        cout<<"dis: ";
//        for(int i = 1; i <= n; ++i) cout<= 0; --i) {
//                cout<<"jump: "< p) {
//                    cout<