UVA - 11354 Bond（最小生成树+LCA+瓶颈路）

题意：N个点，M条路，每条路的危险度为路上各段中最大的危险度。多组询问，点s到点t的所有路径中最小的危险度。

分析：

1、首先建个最小生成树，则s到t的路径一定是危险度最小的。

原因：建最小生成树的最后一步，如果有两个相等的边可以选择，然后将两个连通块连在一起。

那不管选择哪个边，对于分别位于两个连通块的两点来说，这条边都是必经之路，而这个必经之路是这两点路径的危险度中最大的，起决定作用，所以选哪个是一样的。

2、利用lca，在找s和t最近公共祖先的过程中，不断取两者路径中的最大危险度即可。

3、d[k][v] 为点v到它向上走2^k步所到的顶点的路径中最大的危险度。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 50000 + 10;

const int MAXT = 100000 + 10;

using namespace std;

struct Node{

    int a, b;

    Node(int aa, int bb):a(aa), b(bb){}

};

int N, M;

int fa[MAXN];

int d[20][MAXN];

int depth[MAXN];

int parent[20][MAXN];

vector<Node> G[MAXN];

int Find(int x){

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

}

struct Edge{

    int x, y, d;

    void read(){

        scanf("%d%d%d", &x, &y, &d);

    }

    bool operator < (const Edge& rhs)const{

        return d < rhs.d;

    }

}num[MAXT];

void kruskal(){

    for(int i = 0; i < M; ++i){

        int tmpx = Find(num[i].x);

        int tmpy = Find(num[i].y);

        if(tmpx == tmpy) continue;

        G[num[i].x].push_back(Node(num[i].y, num[i].d));

        G[num[i].y].push_back(Node(num[i].x, num[i].d));

        if(tmpx < tmpy) fa[tmpy] = tmpx;

        else fa[tmpx] = tmpy;

    }

}

void dfs(int v, int fa, int deep){

    parent[0][v] = fa;

    depth[v] = deep;

    int len = G[v].size();

    for(int i = 0; i < len; ++i){

        if(G[v][i].a != fa){

            d[0][G[v][i].a] = G[v][i].b;

            dfs(G[v][i].a, v, deep + 1);

        }

    }

}

void LCA_init(){

    dfs(1, -1, 0);

    for(int k = 0; k + 1 < 20; ++k){

        for(int v = 1; v <= N; ++v){

            if(parent[k][v] < 0) parent[k + 1][v] = -1;

            else{

                parent[k + 1][v] = parent[k][parent[k][v]];

                d[k + 1][v] = max(d[k][v], d[k][parent[k][v]]);

            }

        }

    }

}

int lca(int u, int v){

    int ans = 0;

    if(depth[u] > depth[v]) swap(u, v);

    for(int k = 0; k < 20; ++k){

        if(((depth[v] - depth[u]) >> k) & 1){

            ans = max(ans, d[k][v]);

            v = parent[k][v];

        }

    }

    if(u == v) return ans;

    for(int k = 19; k >= 0; --k){

        if(parent[k][u] != parent[k][v]){

            ans = max(ans, d[k][u]);

            ans = max(ans, d[k][v]);

            u = parent[k][u];

            v = parent[k][v];

        }

    }

    ans = max(ans, d[0][u]);

    ans = max(ans, d[0][v]);

    return ans;

}

int main(){

    bool flag = true;

    while(scanf("%d%d", &N, &M) == 2){

        memset(parent, -1, sizeof parent);

        memset(d, 0, sizeof d);

        memset(depth, 0, sizeof depth);

        for(int i = 1; i < MAXN; ++i){

            fa[i] = i;

            G[i].clear();

        }

        for(int i = 0; i < M; ++i){

            num[i].read();

        }

        sort(num, num + M);

        kruskal();

        LCA_init();

        int Q;

        scanf("%d", &Q);

        if(flag) flag = false;

        else printf("\n");

        while(Q--){

            int s, t;

            scanf("%d%d", &s, &t);

            printf("%d\n", lca(s, t));

        }

    }

    return 0;

}

巴特西

UVA - 11354 Bond（最小生成树+LCA+瓶颈路）

最新文章

热门文章