qwb与学姐

Time Limit: 1 Sec Memory Limit: 128 MB

Description

qwb打算向学姐表白，可是学姐已经受够了他的骚扰，于是出了一个题想难住他:
已知一幅n个点m条边的无向图,定义路径的值为这条路径上最短的边的长度，
现在有
k个询问，
询问从A点到B点的所有路径的值的最大值。
qwb听完这个问题很绝望啊,聪明的你能帮帮他吗?

Input

一组数据。
第一行三个整数n，m，k
(1<=N<=50000,m<=200000,k<=100000)。
第2..m+1行：三个正整数：X, Y, and D (1 <=
X <=N; 1 <= Y <= N,1<=D<=2) 表示X与Y之间有一条长度为D的边。
第m+2..m+k+1行：每行两个整数A
B(1<=A,B<=n且A≠B)，意义如题目描述。
保证图连通。

Output

对于每个询问输出一行，一共k行，每行输出A点到B点的所有路径的值的最大值。

Sample Input

Sample Output

6

7

7
分析：题目要求从A到B所有路径中权值最小值的最大值；
　　　我们可以考虑构建一棵最大生成树，这样保证了最大值，然后问题变为A到B求路径上最小值；
代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <bitset>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <cassert>

#include <ctime>

#include<unordered_map>

#define rep(i,m,n) for(i=m;i<=n;i++)

#define mod 1000000007

#define inf 0x3f3f3f3f

#define vi vector<int>

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define pi acos(-1.0)

#define pii pair<int,int>

#define sys system("pause")

const int maxn=5e4+;

const int N=5e2+;

using namespace std;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p%mod;p=p*p%mod;q>>=;}return f;}

int n,m,k,t,fa[][maxn],mi[][maxn],p[maxn],dep[maxn];

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

struct node

{

    int x,y,z;

    bool operator<(const node&p)const

    {

        return z>p.z;

    }

}e[maxn<<];

vector<pii>f[maxn];

void dfs(int x,int y)

{

    dep[x]=dep[y]+;

    fa[][x]=y;

    for(int i=;fa[i-][fa[i-][x]];i++)

    {

        fa[i][x]=fa[i-][fa[i-][x]];

        mi[i][x]=min(mi[i-][x],mi[i-][fa[i-][x]]);

    }

    for(int i=;i<f[x].size();i++)

    {

        int z=f[x][i].fi,w=f[x][i].se;

        if(z==y)continue;

        mi[][z]=w;

        dfs(z,x);

    }

}

int gao(int x,int y)

{

    int ret=1e9;

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

    for(int i=;i>=;i--)if(dep[fa[i][x]]>=dep[y])ret=min(ret,mi[i][x]),x=fa[i][x];

    if(x==y)return ret;

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

    {

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

        {

            ret=min(ret,mi[i][x]);

            ret=min(ret,mi[i][y]);

            x=fa[i][x];

            y=fa[i][y];

        }

    }

    ret=min(ret,mi[][x]);

    ret=min(ret,mi[][y]);

    return ret;

}

int main()

{

    int i,j;

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

    rep(i,,m)

    {

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

    }

    rep(i,,n)p[i]=i;

    sort(e+,e+m+);

    int cnt=;

    rep(i,,m)

    {

        int x=find(e[i].x),y=find(e[i].y);

        if(x!=y)

        {

            p[x]=y;

            f[e[i].x].pb(mp(e[i].y,e[i].z));

            f[e[i].y].pb(mp(e[i].x,e[i].z));

            if(++cnt==n-)break;

        }

    }

    dfs(,);

    while(k--)

    {

        int x,y;

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

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

    }

    return ;

}