UVA 11354 Bond 最小生成树 + lca

题意

给出一张图，q个询问，每次询问给出uv，找出一条路径，使这条路径上的最大边权是两点所有路径中最小，输出这个值

思路

很显然要先求出最小生成树，任意两点在最小生成树上有唯一路径，并且这条路径上的最大边权就是所输出的值，接下来就是如何求出树上任意两点唯一路径中的最大边权了，先把最小生成树转化为有根树，并用fa数组表示u的父亲节点，cost数组表示与父亲节点连的边的边权，dep数组表示这个点的深度，对于每次查询，先把两点的深度调到一样大，同时更新最大边，然后一起向上搜索直到两点的最近公共祖先，同时也更新最大边。这就是最朴素的求LCA的方法。

C++代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + ;

struct Edge{

    int from,to;

    int w,nxt;

}edge[maxn << ],e[maxn << ];

int n , m ;

int pre[maxn];

int fa[maxn],cost[maxn],dep[maxn];

int head[maxn],tot;

void init(){

    tot = ;

    memset(head,-,sizeof head);

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

        pre[i] = i;

    }

}

bool cmp(Edge a,Edge b){

    return a.w < b.w;

}

void add_edge(int u ,int v,int w){

    e[tot].from = u;

    e[tot].to = v;

    e[tot].w = w;

    e[tot].nxt = head[u];

    head[u] = tot ++;

}

inline int find(int x){if(x == pre[x])return x;else return pre[x] = find(pre[x]);}

void kruskal(){

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

    int fu,fv,u,v;

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

        u = edge[i].from;

        v = edge[i].to;

        fu = find(u);

        fv = find(v);

        if(fu != fv){

            pre[fu] = fv;

            add_edge(u,v,edge[i].w);

            add_edge(v,u,edge[i].w);

        }

    }

}

void dfs(int u,int Fa,int step){

    int v;

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

        v = e[i].to;

        if(v ==Fa) continue;

        dep[v] = step;

        fa[v] = u;

        cost[v] = e[i].w;

        dfs(v,u,step + );

    }

}

int lca(int u,int v){

    int du = dep[u];

    int dv = dep[v];

    int res = ;

    while(du > dv){

        res = max(res,cost[u]);

        u = fa[u];

        du --;

    }

    while(dv > du){

        res = max(res,cost[v]);

        v = fa[v];

        dv --;

    }

    while(u != v){

        res = max(res,cost[u]);

        res = max(res,cost[v]);

        u = fa[u];

        v = fa[v];

    }

    return res;

}

int main(){

    int cas = ;

    while(cin >> n >> m){

        if(cas) puts("");

        else cas ++;

        init();

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

            int u , v , w;

            cin >> u >> v >> w;

            edge[i].from = u;

            edge[i].to = v;

            edge[i].w = w;

        }

        //cout << 1 ;

        kruskal();

        fa[] = cost[] = dep[] = ;

        dfs(,-,);

        int q;

        cin >> q;

        while(q--){

            int u , v ;

            cin >> u >> v;

        cout << lca(u,v) << endl;

        }

    }

    return ;

}

巴特西

UVA 11354 Bond 最小生成树 + lca

最新文章

热门文章