BZOJ 3732 Network —— 最小生成树 + 倍增LCA

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3732

Description

给你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点的所有路径中，最长的边最小值是多少？

Input

第一行： 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点的所有路径中，最长的边最小值是多少？

Output

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

Sample Input

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

Sample Output

5
5
5
4
4
7
4
5

HINT

1 <= N <= 15,000

1 <= M <= 30,000

1 <= d_j <= 1,000,000,000

1 <= K <= 15,000

题解：

由题目可知，此图为连通图

所有路径最长边的最小值，即为最小生成树下路径的最长边。因为在最小生成树下，所有边都是最优的，所以保证了最小值。那自然在最小生成树的路径下，最长边即为所求的边。

步骤：

1.构造最小生成树（无根树）。

2.将最小生成树构造为有根数，并用倍增LCA求出每个节点到第2^i个祖先的路径上的最长边。

代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <string>

#include <set>

#define ms(a,b) memset((a),(b),sizeof((a)))

using namespace std;

typedef long long LL;

const int INF = 2e9;

const LL LNF = 9e18;

const int mod = 1e9+7;

const int maxn = 3e4+10;

const int DEG = 20;

struct node

{

    int u, v, w;

    bool operator<(const node &x)const {

        return w<x.w;

    }

}e[maxn];

struct edge

{

    int to, w, next;

}edge[maxn*2];

int n, m,k;

int head[maxn], tot;

int fa[maxn][DEG], deg[maxn], ma[maxn][DEG], be[maxn];

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

void add(int u, int v, int w)

{

    edge[tot].to = v;

    edge[tot].w = w;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void bfs(int root)

{

    queue<int>que;

    deg[root] = 0;

    ma[root][0] = 0;

    fa[root][0] = root;

    que.push(root);

    while(!que.empty())

    {

        int tmp = que.front();

        que.pop();

        for(int i = 1; i<DEG; i++)

            fa[tmp][i] = fa[fa[tmp][i-1]][i-1], ma[tmp][i] = max( ma[tmp][i-1], ma[fa[tmp][i-1]][i-1]);

        for(int i = head[tmp]; i!=-1; i = edge[i].next)

        {

            int v = edge[i].to, w = edge[i].w;

            if(v==fa[tmp][0]) continue;

            deg[v] = deg[tmp]+1;

            fa[v][0] = tmp;

            ma[v][0] = w;

            que.push(v);

        }

    }

}

int LCA(int u, int v)

{

    int ans = 0;

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

    int hu = deg[u], hv = deg[v];

    int tu = u, tv = v;

    for(int det = hv-hu, i = 0; det; det>>=1, i++)

        if(det&1)

            ans = max(ans, ma[tv][i]), tv = fa[tv][i];

    if(tv==tu) return ans;

    for(int i = DEG-1; i>=0; i--)

    {

        if(fa[tu][i]==fa[tv][i]) continue;

        ans = max(ans, max( ma[tu][i], ma[tv][i] ) );

        tu = fa[tu][i];

        tv = fa[tv][i];

    }

    return ans = max(ans, max( ma[tu][0], ma[tv][0]) );

}

int main()

{

    tot = 0;

    ms(head, -1);

    ms(ma,0);

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

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

        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

    sort(e,e+m);

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

        be[i] = i;

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

    {

        int u = find(e[i].u), v = find(e[i].v);

        if(u!=v)

        {

            be[u] = v;

            add(e[i].u, e[i].v, e[i].w);

            add(e[i].v, e[i].u, e[i].w);

        }

    }

    bfs(1);

    for(int i = 0; i<k; i++)

    {

        int u, v;

        scanf("%d%d",&u,&v);

        printf("%d\n",LCA(u,v));

    }

}

巴特西