Kruskal 重构树

Kruskal 重构树的过程就是在 Kruskal 算法 merge 的时候新建一颗树, 比如对于枚举到的边 (A, B):

我们新建一个点与其相连:

若边有边权, 则把 T 的 <stron> 设为其边权</stron>

我们来看看这样做的好处, 比如对于下面这个在最小生成树上的两个边:

经过上面的加点连边, 就可以得到:

其中 P 的点权为 $3$ , Q 的点权为 $4$

注意到Kruskal枚举的边的边权都是单调递增的, 所以按照上面的过程(最小生成树)构建的Kruskal重构树一定是个 大根堆

由于这是一棵树, 考虑这个树有什么特殊性质.

对于树上两点的 LCA, 在原图中的意义就是 两点间所有路径的最小边权的最大值

代码也很好写:

int ncnt;
void kruskal () {
    std::sort(data + 1, data + m + 1, [] (const E &a, const E &b) -> bool { return a.w < b.w; });
    ncnt = n;
    up (i, 1, m) {
        int _u = find(data[i].u), _v = find(data[i].v);
        if (_u == _v) continue;
        val[++ncnt] = data[i].w; // 点权
        fa[_u] = fa[_v] = fa[ncnt] = ncnt;
        add(_u, ncnt); add(ncnt, _u); // 加边
        add(_v, ncnt); add(ncnt, _v); // 加边
    }
}

下面来看一个简单的例题:

例题

「NOIP2013」货车运输

暂且就不放题面了, ~~因为太常见了~~

题面中求的是最大边权的最小值, 不过不影响重构树的使用

代码:

const int N = 200000 + 10;
const int M = 200000 + 10; 

struct E {
    int u, v, w;
    E () {}
    E (int _u, int _v, int _w) : u(_u) , v(_v) , w(_w) {}
};

struct Edge {
    int v;
    int next;
    Edge () {}
    Edge (int _v, int _n) : v(_v) , next(_n) {}
};

E data[M];

int tot;
int hd[N];
Edge e[M << 1];
int val[N];

inline void add (int u, int v) { e[++tot] = Edge(v, hd[u]); hd[u] = tot;}

int n, m;
int fa[N];

inline void init() { up (i, 1, n) fa[i] = i; }
inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int siz[N], vis[N];
int top[N], son[N];
int dep[N];
int Fa[N];

void dfs1 (int u, int fa = 0) {
    siz[u] = vis[u] = 1;
    for (int i = hd[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (v == fa) continue;
        Fa[v] = u;
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
} 

void dfs2 (int u, int ctop = 0) {
    top[u] = ctop;
    if (son[u]) dfs2(son[u], ctop);
    for (int i = hd[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (v == Fa[u]) continue;
        if (v ^ son[u]) dfs2(v, v);
    }
}

int ncnt;
void kruskal () {
    std::sort(data + 1, data + m + 1, [] (const E &a, const E &b) -> bool { return a.w > b.w; });
    ncnt = n;
    up (i, 1, m) {
        int _u = find(data[i].u), _v = find(data[i].v);
        if (_u == _v) continue;
        val[++ncnt] = data[i].w;
        fa[_u] = fa[_v] = fa[ncnt] = ncnt;
        add(_u, ncnt); add(ncnt, _u);
        add(_v, ncnt); add(ncnt, _v);
    }
}

void pre() {
    up (i, 1, ncnt) {
        if (vis[i]) continue;
        dfs1(find(i)); dfs2(find(i));
    }
}

int lca (int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) u = Fa[top[u]];
        else v = Fa[top[v]];
    }
    return dep[u] < dep[v] ? u : v;
}

int main () {
    init();
    n = read(); m = read();
    int u, v, w;
    up (i, 1, m) {
        u = read(); v = read(); w = read();
        data[i] = E(u, v, w);
    }
    init();
    kruskal();
    pre();
    int q = read();
    while (q --> 0) {
        u = read(); v = read();
        if (find(u) != find(v)) printf("-1\n");
        else printf("%d\n", val[lca(u, v)]);
    }
    return 0;
}

「NOI2018」归程

题面仍然略了(

大概这类边权不好处理的就可以考虑转化为点权能不能做(

也是直接重构树

(Luogu数据好氵....建议去 uoj 交一下)

代码:

#define int long long

const int N = 500000 + 10;
const int M = 1000000 + 10;
const int logN = 20 + 2;

int n, m;

struct E {
    int u, v, w;
    E () {}
    E (int _u, int _v, int _w) : u(_u) , v(_v) , w(_w) {}
};

struct Edge {
    int v, w;
    int next;
    Edge () {}
    Edge (int _v, int _w, int _n) : v(_v), w(_w), next(_n) {}
};

E data[M];

int tot;
int hd[N];
Edge e[M];
int val[N];

inline void add (int u, int v, int w) { e[++tot] = Edge(v, w, hd[u]); hd[u] = tot;}

int fa[N];
int f[N][logN];

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

int d[N];
bool vis[N];

void dij (int S) {
    memset (d, 0x3f, sizeof d); mem(vis);
    std::priority_queue <std::pair<int, int> > q;
    q.push(mp(0, S)); d[S] = 0;
    while (!q.empty()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = hd[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (d[v] > d[u] + e[i].w) {
                d[v] = d[u] + e[i].w;
                q.push(mp(-d[v], v));
            }
        }
    }
}

void kru () {
    std::sort (data + 1, data + m + 1, [] (const E &a, const E &b) -> bool { return a.w > b.w; });
    int cnt = n;
    up (i, 1, m) {
        int _u = find(data[i].u), _v = find(data[i].v);
        if (_u == _v) continue;
        val[++cnt] = data[i].w;
        fa[_u] = fa[_v] = f[_u][0] = f[_v][0] = cnt;
        d[cnt] = std::min(d[_u], d[_v]);
    }
    for (int i = 1; (1 << i) <= cnt; i++)
        up (j, 1, cnt) f[j][i] = f[f[j][i - 1]][i - 1];
}

inline int solve (int x, int y) {
    down(i, 19, 0)
        if (f[x][i] && val[f[x][i]] > y) x = f[x][i];
    return d[x];
}

inline void init() {
    tot = 0; mem(hd);
    up (i, 1, 2 * n) fa[i] = i;
}

signed main () {
    int T = read();
    while (T --> 0) {
        n = read(); m = read();
        init();
        int u, v, w, h;
        up (i, 1, m) {
            u = read(); v = read(); w = read(); h = read();
            add (u, v, w); add(v, u, w);
            data[i] = E(u, v, h);
        }
        dij(1);
        kru();
        int lst = 0;
        int q, k, s, x, y;
        q = read(); k = read(); s = read();
        while (q --> 0) {
            x = read(); y = read();
            x = (x + k * lst - 1) % n + 1;
            y = (y + k * lst) % (s + 1);
            lst = solve(x, y);
            print(lst); putchar('\n');
        }
    }
    return 0;
}

「重构树」Kruskal重构树入门笔记

Kruskal 重构树

例题

「NOIP2013」货车运输

「NOI2018」归程