3732: Network

题目连接：

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 < = 15,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

题意

题解：

求最小生成树之后，查询链上最大边的权值。

树链剖分或者倍增都可以。

代码

#include<bits/stdc++.h>

using namespace std;

const int N=200500;

int n,m;

struct node

{

    int x,y,c,no;

}E[N<<1];

int pre[N],to[N<<1],w[N<<1],nxt[N<<1],k;

int fa[N],lca[N][22],p[N][22],dep[N],cnt;

void makeedge(int x,int y,int c)

{

    to[cnt]=x;w[cnt]=c;nxt[cnt]=pre[y];pre[y]=cnt++;

    to[cnt]=y;w[cnt]=c;nxt[cnt]=pre[x];pre[x]=cnt++;

}

int getfather(int x)

{

    if(fa[x]==x) return fa[x];else return fa[x]=getfather(fa[x]);

}

void dfs(int x)

{

    for(int it=pre[x];~it;it=nxt[it])

    {

        int y=to[it],c=w[it];

        if(y==lca[x][0]) continue;

        dep[y]=dep[x]+1,lca[y][0]=x,p[y][0]=c;

        dfs(y);

    }

}

int query(int x,int y)

{

    int ret=0;

    if(dep[x]<dep[y]) swap(x,y);

    for(int i=21;i>=0;i--)

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

            ret=max(ret,p[x][i]),x=lca[x][i];

    if(x==y) return ret;

    for(int i=21;i>=0;i--)

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

            ret=max(ret,max(p[x][i],p[y][i])),x=lca[x][i],y=lca[y][i];

    ret=max(ret,max(p[y][0],p[x][0]));

    return ret;

}

bool cmp(node t1,node t2)

{

    return t1.c<t2.c;

}

int main()

{

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

    memset(pre,-1,sizeof(pre));

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

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

    {

        scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].c);

        E[i].no=i;

    }

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

    long long tot=0;

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

    {

        int x=E[i].x,y=E[i].y;

        int f1=getfather(x),f2=getfather(y);

        if(f1!=f2)

        {

            fa[f2]=f1;

            tot+=(long long)E[i].c;

            makeedge(x,y,E[i].c);

        }

    }

    dfs(1);

    for(int j=1;j<=21;j++)

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

            if(lca[i][j-1])

            {

                lca[i][j]=lca[lca[i][j-1]][j-1];

                p[i][j]=max(p[i][j-1],p[lca[i][j-1]][j-1]);

            }

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

    {

        int x,y;

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

        printf("%d\n",query(x,y));

    }

}