洛谷p1967货车运输（kruskal重构树）

时间：2024-05-01 13:42:17

题面

题解中有很多说最优解是kruskal重构树

所以

抽了个早自习看了看这方面的内容

我看的博客

感觉真的挺好使的

首先对于kruskal算法来说

是基于贪心的思想把边权排序用并查集维护是否是在同一棵树上

对于kruskal重构树来说

按不同边权顺序排序可相应的得到最大边权的最小值 、最小边权的最大值等问题

建树过程：

排好序后， 遍历， 若两条边u， v不在同一并查集内， 那么就新建一个节点， 这个节点的点权就代表u到v的边权， 同时将这三个点都加入同一并查集

需要注意

最后建立出来的可能是森林，也就是并不是所有的点的根都是相同的

此时

可以用一个vis数组来确保所有的点都被遍历过了

1.若按照边权的升序排列

那么最后可以求得最大边权的最小值

感性理解一下

因为最后是要求最小值

所以

建一棵最小生成树

此时最大的边权就是所有别的建树方法中的最小值

2.若按照边权的降序排列

同上

要求最小边权的最大值

最后答案是最大值

那么建一棵最大生成树

关于为什么lca是答案：

感性理解一下

如果我们建的树是最小生成树

那么

显然边权越大深度越深

我们是想按着边权尽量小的走

lca(u, v)是原图u->v节点深度最小的点

所以就是他了

关于此题的代码：

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = ;

int n, m, sum, fa[N], cnt, size[N], top[N], dad[N], head[N], va[N], tot, q, deep[N], vis[N], son[N];

struct Edge{

    int from, to, w;

}e[N << ];

struct Node {

    int nxt, to, w;

}ee[N];

void add(int x, int y) {

    ee[++tot].nxt = head[x];

    ee[tot].to = y;

    head[x] = tot;

}

bool cmp(Edge x, Edge y) {

    return x.w > y.w;

}

int find(int x) {

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

}

void dfs(int u, int pa) {

    size[u] = ;vis[u] = ;

    for(int i = head[u]; i; i = ee[i].nxt) {

        int v = ee[i].to;

        if(v == pa) continue;

        deep[v] = deep[u] + , dad[v] = u;

        dfs(v, u);

        size[u] += size[v];

        if(size[v] > size[son[u]]) son[u] = v;

    }

}

void dfs1(int u, int tp) {

    top[u] = tp;

    if(son[u]) dfs1(son[u], tp);

    for(int i = head[u]; i; i = ee[i].nxt) {

        int v = ee[i].to;

        if(v == dad[u] || v == son[u]) continue;

        dfs1(v, v);

    }

}

int lca(int x, int y) {

    while(top[x] != top[y]) {

        if(deep[top[x]] < deep[top[y]]) swap(x, y);

        x = dad[top[x]];

    }

    return deep[x] > deep[y] ? y : x;

}

int main() {

    scanf("%d%d", &n, &m);

    for(int i = ; i <= n; i++) fa[i] = i;

    cnt = n;

    for(int i = ; i <= m; i++)

        scanf("%d%d%d", &e[i].from, &e[i].to, &e[i].w);

    sort(e + , e +  + m, cmp);

    for(int i = ; i <= m; i++) {

        int fx = find(e[i].from), fy = find(e[i].to);

        if(fx != fy) {

            va[++cnt] = e[i].w;

            fa[fx] = fa[fy] = fa[cnt] = cnt;

            add(fx, cnt);add(cnt, fx);

            add(fy, cnt);add(cnt, fy);

        }

    }

    for(int i = ; i <= cnt; i++)

        if(!vis[i]) {

            int f = find(i);

            dfs(f, ), dfs1(f, f);

        }

    /*for(int i = 1; i <= cnt; i++)

        printf("%d ", size[i]);*/

    scanf("%d", &q);

    while(q--) {

        scanf("%d%d", &n, &m);

        if(find(n) != find(m)) printf("-1\n");

        else printf("%d\n", va[lca(n, m)]);

    }

    return ;

}

谢谢收看， 祝身体健康！

相关文章