首页 > 代码库 > qwb与学姐

qwb与学姐

2024-09-29 17:44:01   221人阅读

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<=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
分析：题目要求从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+10;const int N=5e2+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}int n,m,k,t,fa[20][maxn],mi[20][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<<2];vector<pii>f[maxn];void dfs(int x,int y){    dep[x]=dep[y]+1;    fa[0][x]=y;    for(int i=1;fa[i-1][fa[i-1][x]];i++)    {        fa[i][x]=fa[i-1][fa[i-1][x]];        mi[i][x]=min(mi[i-1][x],mi[i-1][fa[i-1][x]]);    }    for(int i=0;i<f[x].size();i++)    {        int z=f[x][i].fi,w=f[x][i].se;        if(z==y)continue;        mi[0][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=19;i>=0;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=19;i>=0;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[0][x]);    ret=min(ret,mi[0][y]);    return ret;}int main(){    int i,j;    scanf("%d%d%d",&n,&m,&k);    rep(i,1,m)    {        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);    }    rep(i,1,n)p[i]=i;    sort(e+1,e+m+1);    int cnt=0;    rep(i,1,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-1)break;        }    }    dfs(1,0);    while(k--)    {        int x,y;        scanf("%d%d",&x,&y);        printf("%d\n",gao(x,y));    }    return 0;}

qwb与学姐


联系
我们