【bzoj3732】Network 最小生成树+倍增LCA

题目描述

给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。
图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).

现在有 K个询问 (1 < = K < = 20,000)。
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？

输入

第一行： N, M, K。
第2..M+1行: 三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。
第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中，最长的边最小值是多少？

输出

对每个询问，输出最长的边最小值是多少。

样例输入

6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1

样例输出

5
5
5
4
4
7
4
5

题解

最小生成树+倍增LCA

这题和noip2013货车运输正好相反，那道题是求最大的最小值，而这题是求最小的最大值。

可以证明这样的路径一定是在原图的最小生成树上，于是Kruskal求一下最小生成树。

然后跑倍增LCA即可。

#include <cstdio>

#include <algorithm>

using namespace std;

struct data

{

    int x , y , z;

}a[30010];

int f[15010] , head[15010] , to[30010] , len[30010] , next[30010] , cnt , log[15010] , deep[15010] , fa[15010][20] , maxn[15010][20];

bool cmp(data a , data b)

{

    return a.z < b.z;

}

int find(int x)

{

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

}

void add(int x , int y , int z)

{

    to[++cnt] = y;

    len[cnt] = z;

    next[cnt] = head[x];

    head[x] = cnt;

}

void dfs(int x)

{

    int i;

    for(i = 1 ; i <= log[deep[x]] ; i ++ )

        fa[x][i] = fa[fa[x][i - 1]][i - 1] , maxn[x][i] = max(maxn[x][i - 1] , maxn[fa[x][i - 1]][i - 1]);

    for(i = head[x] ; i ; i = next[i])

    {

        if(to[i] != fa[x][0])

        {

            fa[to[i]][0] = x;

            maxn[to[i]][0] = len[i];

            deep[to[i]] = deep[x] + 1;

            dfs(to[i]);

        }

    }

}

int query(int x , int y)

{

    int i , ans = 0;

    if(deep[x] < deep[y])

        swap(x , y);

    for(i = log[deep[x] - deep[y]] ; i >= 0 ; i -- )

        if(deep[x] - (1 << i) >= deep[y])

            ans = max(ans , maxn[x][i]) , x = fa[x][i];

    for(i = log[deep[x]] ; i >= 0 ; i -- )

        if(fa[x][i] != fa[y][i])

            ans = max(ans , max(maxn[x][i] , maxn[y][i])) , x = fa[x][i] , y = fa[y][i];

    if(x != y)

        ans = max(ans , max(maxn[x][0] , maxn[y][0]));

    return ans;

}

int main()

{

    int n , m , k , i , num = 0 , tx , ty;

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

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

        scanf("%d%d%d" , &a[i].x , &a[i].y , &a[i].z);

    sort(a + 1 , a + m + 1 , cmp);

    for(i = 1 ; i <= n ; i ++ )

        f[i] = i;

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

    {

        tx = find(a[i].x) , ty = find(a[i].y);

        if(tx != ty)

        {

            f[tx] = ty;

            add(a[i].x , a[i].y , a[i].z) , add(a[i].y , a[i].x , a[i].z);

            num ++ ;

            if(num == n - 1)

                break;

        }

    }

    for(i = 2 ; i <= n ; i ++ )

        log[i] = log[i >> 1] + 1;

    dfs(1);

    while(k -- )

    {

        scanf("%d%d" , &tx , &ty);

        printf("%d\n" , query(tx , ty));

    }

    return 0;

}

巴特西

【bzoj3732】Network 最小生成树+倍增LCA

最新文章

热门文章