qwb与学姐

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 149  Solved: 54

[][][]

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<=215) 表示X与Y之间有一条长度为D的边。 

第m+2..m+k+1行： 每行两个整数A B(1<=A,B<=n且A≠B)，意义如题目描述。

保证图连通。

Output

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

Sample Input

4 5 31 2 61 3 82 3 42 4 53 4 72 31 43 4

Sample Output

677 【分析】给你一个连通无向图，然后K次询问，每次给出两个点U,V，一条路径中最小的边称为路径的值，问你从U到V的所有路径中，  路径的值最大是多少。  要是只有一次询问的话，还能二分搞搞...这1e5次询问太TM恶心了。我们二分的时候是二分答案，然后遍历所有的点，只走权值  大于等于二分值的边是吧。也就是说如果我们加了这条权值为二分值的边，那么U,V就连通了。那么我们可以按权值从大到小排序，  将边连接的两个点加入到带权并查集，并且维护秩，及带秩带权并查集，那么我们查询的时候只用依次向上，直到LCA，取权值的  最小值。写完代码我才发现，我好像写了个最大生成树，由于我这是带秩的，所以询问的时候尽管是暴力，但也是log的。

#include 
     
      #define mp make_pair#define pb push_back#define met(a,b) memset(a,b,sizeof a)#define sys system("pause")using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair
      
       pii;const int N = 5e4+5;const int M = 2e5+50;const int mod = 1e9+7;int n,m,k,root;int dep[N],parent[N];int dis[N];vector
       
        vec[N];struct Edge{    int u,v,cost;    bool operator<(const Edge &e)const{        return cost>e.cost;    }} edg[M];int Find(int x){    return x==parent[x]?x:Find(parent[x]);}void Union(int x,int y,int w){    x=Find(x);    y=Find(y);    if(dep[x]<=dep[y]){        parent[x]=y;        dis[x]=w;        if(dep[x]==dep[y])dep[y]++;    }    else{        parent[y]=x;        dis[y]=w;    }}void dfs(int u){    for(int i=0; i
        
         dep[y]){        ret=min(ret,dis[x]);        x=parent[x];    }    while(x!=y){        ret=min(ret,min(dis[x],dis[y]));        x=parent[x];        y=parent[y];    }    return ret;}int main(){    scanf("%d%d%d",&n,&m,&k);    for(int i=1; i<=n; i++)parent[i]=i;    for(int i=1; i<=m; i++){        scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].cost);    }    sort(edg+1,edg+m+1);    for(int i=1; i<=m; i++){        if(Find(edg[i].u)!=Find(edg[i].v)){            Union(edg[i].u,edg[i].v,edg[i].cost);        }    }    for(int i=1; i<=n; i++){        if(parent[i]==i)root=i;        else vec[parent[i]].pb(mp(i,dis[i]));    }    dep[root]=1;    dfs(root);    while(k--){        int u,v;        scanf("%d%d",&u,&v);        printf("%d\n",solve(u,v));    }    return 0;}