Luogu P1967 货车运输

佚名 6年前 (2019-05-15) 随笔 1733人围观抢沙发百度已收录

P1967 货车运输

简述题意：给定一个图，求两点之间所有路径上/最短边最大的路一条路径/的最短边（突然绕我应该表述复杂了）

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

做法：最大生成树+树上倍增

先跑一遍最大生成树。可以证明答案一定在最大生成树上。

建树，树上跑倍增\(LCA\)，取两点路径的\(min\)值就可以了w

#include <algorithm>
#include <iostream>
#include <cstring> 
#include <cstdio>
#include <cmath>
#define MAXN 10233
using namespace std;


struct qwq
{
    int u,v,w;
}a[523333];
struct qvq
{
    int n,t,w;
}e[523333];
int n,m;
int f[MAXN];
int q;
int tot=0;
struct tree
{
    int f,w;
}fa[MAXN][22];
int head[MAXN],deep[MAXN];
bool vis[MAXN]={};



bool cmp(qwq x,qwq y)
{
    return x.w>y.w;
}
int find(int x)
{
    if (f[x]==x) return x;
    return f[x]=find(f[x]);
}
void add(int f,int t,int w)
{
    e[++tot].n=head[f];
    e[tot].t=t;
    e[tot].w=w;
    head[f]=tot;
}
void kruscal()
{
    int sum=0;
    for (int i=1,xx,yy;i<=m;i++)
    {
        xx=find(a[i].u);
        yy=find(a[i].v);
        if (xx!=yy)
        {
            sum++;
            f[xx]=yy;
            add(a[i].u,a[i].v,a[i].w);
            add(a[i].v,a[i].u,a[i].w);
        }
        if (sum==n-1)
        {
            break;
        }
    }
}
void dfs(int ed)
{
    int t;
    vis[ed]=1;
    for (int i=head[ed];i;i=e[i].n)
    {
        t=e[i].t;
        if (vis[t]) continue;
        deep[t]=deep[ed]+1;
        fa[t][0].f=ed;
        fa[t][0].w=e[i].w;
        dfs(t);
    }
}
int lca(int x,int y)
{
    if (find(x)!=find(y)) return -1;
    int ans=999999999;
    if (deep[x]>deep[y]) swap(x,y);
    for (int i=20;i>=0;i--)
    {
        if (deep[fa[y][i].f]>=deep[x])
        {
            ans=min(ans,fa[y][i].w);
            
            y=fa[y][i].f;
        }
    }
    if (x==y) return ans;
    for (int i=20;i>=0;i--)
    {
        if (fa[x][i].f!=fa[y][i].f)
        {
            ans=min(ans,min(fa[x][i].w,fa[y][i].w));
            x=fa[x][i].f; y=fa[y][i].f;
        }
    }
    ans=min(ans,min(fa[x][0].w,fa[y][0].w));
    return ans;
}
int main()
{
//  freopen("qwq.txt","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
    }
    sort(a+1,a+m+1,cmp);
    
    kruscal();
    for (int i=2;i<=n;i++)
    {
        if (!vis[i])
        {
            deep[i]=1;
            dfs(i);
            fa[i][0].f=i;
            fa[i][0].w=999999999;
        }
    }
    for (int i=1;i<=20;i++)
    {
        for (int j=1;j<=n;j++)
        {
            fa[j][i].f=fa[fa[j][i-1].f][i-1].f;
            fa[j][i].w=min(fa[j][i-1].w, fa[fa[j][i-1].f][i-1].w);
        }
    }



//     Debug
//  for (int i=1;i<=tot;i++)
//  {
//      printf("::%d %d %d\n",e[i].n,e[i].t,e[i].w);
//  }
//  printf("\n");
//  for (int i=1;i<=n;i++)
//  {
//      printf("%d ",head[i]);
//  }
//  printf("\n");
//  for (int i=1;i<=n;i++)
//  {
//      for (int j=1;j<=log2(n);j++)
//      printf("%d %d ",fa[i][j].f,fa[i][j].w);
//  }
//  printf("\n");
//    for (int i=1;i<=n;i++)
//    {
//      printf("\n::%d : %d  %d\n",i,fa[i][0].f,deep[i]);
//  }
//    printf("\n\n\n%d\n\n\n",fa[1][0].f);



    scanf("%d",&q);
    for (int i=1,xx,yy;i<=q;i++)
    {
        scanf("%d%d",&xx,&yy);
        printf("%d\n",lca(xx,yy));
    }
    return 0;
}