[NOI2018] 归程 [Kruskal 重构树/倍增/最短路]

就此也把Kruskal重构树的性质总结一下...

Problem

https://www.luogu.org/problemnew/show/P4768

Solution


Kruskal重构树可以用于求解两点之间任意路径最大边的最小值。

如果是离线的话,可以Kruskal做就行了。也是一个贪心的思想。

我们按照kruskal求最小⽣成树的方式加边,但每次在加边时,新建⼀个节点,然后把两个联通块(其实是两棵⼆叉树)的根节点作为其左右儿⼦,把边权赋值给新建节点。那么我们可以发现这棵树有几个性质。

  1. 是⼀棵⼆叉树;
  2. 满⾜父节点的值⼤于等于儿⼦节点,是⼀个大顶堆,这是最关键的⼀点;
  3. 原图上任意两点间路径最长边的最小值等于其lca的值;

当然如果是从大到小建的话,原理也一样。本题需要倒着建,然后lca的意义就变成了路上最短边的最大值。也就是说u,v的这个值如果>T,则u,v联通。

则对于点权>T的子树,其中的叶子节点属于一个连通块(因为任意叶子节点的任意路径的最短边的最大值>T),而子树肯定不能与子树外的结点构成连通块(<=T)。

所以只需预处理出每个点到1的最短路值,再建Kruskal重构树预处理子树min值,查询时倍增即可。

Code

程序好像已经经过了luogu数据检验可以放心(雾)

luogu加题速度很快啊,给管理员点赞

// Code by ajcxsu
// Problem: return

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
using namespace std;
typedef long long ll;

template<typename T> void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=4e5+10, M=1e6+10;
int h[N], to[M], nexp[M], p=1;
ll W[M], f[N], nw[N];
inline void ins(int a, int b, ll w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
struct Edge { int u, v; ll w; } e[M];
bool cmp(const Edge &a, const Edge &b) { return a.w>b.w; }
int n, m;
ll U;

ll dist[N];
bool S[N];
typedef pair<ll, int> mpair;
void SPFA() {
    CLR(dist, 0x3f), CLR(S, 0);
    priority_queue<mpair, vector<mpair>, greater<mpair> > pq;
    pq.push(mpair(0, 1));
    dist[1]=0;
    int na;
    for(int i=1;i<=n;i++) {
        while(S[pq.top().second] || pq.top().first>dist[pq.top().second]) pq.pop();
        na=pq.top().second, S[na]=1;
        for(int u=h[na];u;u=nexp[u])
            if(dist[to[u]]>dist[na]+W[u] && !S[to[u]])
                dist[to[u]]=dist[na]+W[u], pq.push(mpair(dist[to[u]], to[u]));
    }
}

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

const int OP=22;
int gup[N][OP];
void dfs(int x) {
    for(int u=h[x];u;u=nexp[u])
        dfs(to[u]), f[x]=min(f[x], f[to[u]]), gup[to[u]][0]=x;
    if(x<=n) f[x]=dist[x];
}

int main() {
    int T;
    gn(T);
    while(T--) {
        CLR(h, 0), p=1;
        gn(n), gn(m);
        int u, v, w, a;
        for(int i=1;i<=m;i++)
            gn(u), gn(v), gn(w), gn(a),
            ins(u, v, w), ins(v, u, w),
            e[i]={u, v, a};
        sort(e+1, e+1+m, cmp);
        SPFA();
        int idx=n;
        CLR(h, 0), CLR(fa, 0), p=1;
        for(int i=1;i<=n;i++) W[i]=0;
        for(int i=1;i<=m;i++) {
            int af=Find(e[i].u), bf=Find(e[i].v);
            if(af==bf) continue;
            fa[af]=fa[bf]=++idx;
            ins(idx, af, 0), ins(idx, bf, 0);
            nw[idx]=e[i].w;
        }
        CLR(gup, 0), CLR(f, 0x3f);
        dfs(idx);
        for(int j=1;j<OP;j++)
            for(int i=1;i<=idx;i++)
                gup[i][j]=gup[gup[i][j-1]][j-1];
        ll Q,K,S;
        gn(Q), gn(K), gn(S);
        ll lastans=0;
        while(Q--) {
            gn(u), gn(U);
            u=(u+K*lastans-1)%n+1;
            U=(U+K*lastans)%(S+1);
            for(int j=OP-1;j>=0;j--)
                if(nw[gup[u][j]]>U) u=gup[u][j];
            printf("%lld\n", lastans=f[u]);
        }
    }
    return 0;
}

本文链接:https://acxblog.site/archives/sol-luogu-4768.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。

    Dof
    Dof  2018-07-23, 16:44

    博主怎么写Spfa的呀,不行啊~~~
    (出题人:关于SPFA,它死了~~

      ajcxsu
      ajcxsu  2018-07-23, 19:49

      表面上是SPFA其实是Dijkstra(雾)
      可能是函数名忘记改qwq

        Dof
        Dof  2018-07-25, 16:13

        哎呀呀,我好像看错了呀 (⊙o⊙)