题解 P1967 【货车运输】

· · 题解

写一个树剖的题解吧

先分析下题意，一个图，若干点，若干边，查询若干链

首先，很清楚，最大生成树

这样得到若干棵树

然后，建一个虚根，将这些树变成一棵树

查询的话，就是一条链上的各边的最小值，树剖，然后线段树维护rmq

另，树剖维护点权，而该题给的是边权，所以要转换一下

我是这样做的，定义一个点的点权为为其到其父节点的边权，根节点就是无穷大

代码如下,不喜勿喷：

#include<iostream>
#include<algorithm>
using namespace std;
struct ed
{
    int v,x,y;
};
ed e[500008];
int n,m;
bool cmp(const ed &a,const ed &b)
{
    return a.v>b.v;
}
int hea[50005],nex[30005],poi[30005],val[30005],tot;
void work(int i,int j,int v)
{
    tot++;
    val[tot]=v;
    poi[tot]=j;
    nex[tot]=hea[i];
    hea[i]=tot;
}
int fa[50005],dep[50005],top[50005],size[50005],xl[50005],num,pos[50005],son[50005];
int fd(int x)
{
    if(fa[x]!=x)
     fa[x]=fd(fa[x]);
    return fa[x];
}
int dc[50005];
int s[400005];
void build(int p,int l,int r)
{
    if(l==r)
    {
        s[p]=dc[xl[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build((p<<1)|1,mid+1,r);
    s[p]=min(s[p<<1],s[(p<<1)|1]);
}
int getmin(int p,int l,int r,int al,int ar)
{
    if(l>=al&&r<=ar)
    {
        return s[p];
    }
    int minn=372199;
    int mid=(l+r)>>1;
    if(al<=mid)
     minn=min(minn,getmin(p<<1,l,mid,al,ar));
    if(ar>mid)
     minn=min(minn,getmin((p<<1)|1,mid+1,r,al,ar));
    return minn;
}
void dfs1(int node)
{
    int b=hea[node];
    while(b)
    {
        int u=poi[b];
        if(u==fa[node])
        {
            b=nex[b];
            continue;
        }
        size[u]=1;
        fa[u]=node;
        dc[u]=val[b];
        dep[u]=dep[node]+1;
        dfs1(u);
        size[node]+=size[u];
        if(size[son[node]]<size[u])
         son[node]=u;
        b=nex[b];
    }
}
void dfs2(int node)
{
    num++;
    pos[node]=num,xl[num]=node;
    if(son[node])
    {
        top[son[node]]=top[node];
        dfs2(son[node]);
    }
    int b=hea[node];
    while(b)
    {
        int u=poi[b];
        if(u==son[node]||u==fa[node])
        {
            b=nex[b];
            continue;
        }
        top[u]=u;
        dfs2(u);
        b=nex[b];
    }
}
int query(int x,int y)
{
    int minn=372199;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        {
            int t=x;
            x=y;
            y=t;
        }
        minn=min(minn,getmin(1,1,n+1,pos[top[x]],pos[x]));
        x=fa[top[x]];
    }
    if(x==y)
     return minn;
    if(dep[x]<dep[y])
    {
        int t=x;
        x=y;
        y=t;
    }
    minn=min(minn,getmin(1,1,n+1,pos[y]+1,pos[x]));
    return minn;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
     cin>>e[i].x>>e[i].y>>e[i].v;
    for(int i=1;i<=n;i++)
     fa[i]=i;
    sort(e+1,e+m+1,cmp);
    int rest=n-1;
    for(int i=1;i<=m;i++)
    {
        if(!rest)
         break;
        int xx=e[i].x,yy=e[i].y;
        int fx=fd(xx),fy=fd(yy);
        if(fx!=fy)
        {
            fa[fx]=fy;
            work(xx,yy,e[i].v);
            work(yy,xx,e[i].v);
        }
    }
    int root=n*3;
    for(int i=1;i<=n;i++)
     if(fa[i]==i)
     {
        fa[i]=root;
        work(root,i,-1);
     }  
     else
      fa[i]=0;
    fa[root]=root;
    dfs1(root);
    dfs2(root);
    build(1,1,n+1);
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int x,y;
        cin>>x>>y;
        int qq=query(x,y);
        cout<<qq<<endl;
    }
}