题面

题目描述

$A$ 国有 $n$ 座城市，编号从 $1$ 到 $n$ ，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 $q$ 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：

第一行有两个用一个空格隔开的整数 $n,m$ ，表示 $A$ 国有 $n$ 座城市和 $m$ 条道路。

接下来 $m$ 行每行 $3$ 个整数 $x, y, z$ ，每两个整数之间用一个空格隔开，表示从 $x$ 号城市到 $y$ 号城市有一条限重为 $z$ 的道路。注意： $x$ 不等于 $y$ ，两座城市之间可能有多条道路 。

接下来一行有一个整数 $q$ ，表示有 $q$ 辆货车需要运货。

接下来 $q$ 行，每行两个整数 $x,y$ ，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，注意： $x$ 不等于 $y$ 。

输出格式：

共有 $q$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出 $-1$ 。

输入输出样例

输入样例：

输出样例：

说明

对于 $30 % $ 的数据， $0<n<1,000,0<m<10,000,0<q<1,000$ ；

对于 $60 % $ 的数据， $0<n<1,000,0<m<50,000,0<q<1,000$ ；

对于 $100 % $ 的数据， $0<n<10,000,0<m<50,000,0<q<30,000,0 \leq z \leq 100,000$ 。

思路

七月份的时候刚做这道题，用的是最大生成树+树链剖分。今天为了写[NOI2018]归程，把这道题当作了 $Kruskal$ 重构树的板子题，在这里讲解一下 $Kruskal$ 重构树的写法。

在 $Kruskal$ 算法的过程中，如果要在 $x,y$ 两节点之间连边，那么就把并查集中 $x,y$ 的父节点分别连向一个新节点，这个新节点有一个权值，该点权为这条边的长度。也就是说这样子做：

sort(edge,edge+m);

for(int i=1;i<=n;i++) f[i]=i;

for(int i=0;i<m;i++)

{

    int fx=fd(edge[i].u),fy=fd(edge[i].v);

    if(fx!=fy)

    {

        a[++n]=edge[i].d;

        f[fx]=f[fy]=f[n]=n;

        add_edge(fx,n),add_edge(fy,n);

    }

}

这样子建出来的树有以下特点：

该树共有 $2n-1$ 个结点
- 原来有 $n$ 个点，一共连了 $n-1$ 条边，每条边新建一个结点，所以 $n+n-1=2n-1$
原有点全在叶子节点上
- 按照上述写法， f[fx]=f[fy]=f[n]=n; ，是从 $fx,fy$ 向 $n$ 连边，没有结点向结点连边
该树是一颗二叉树
- 显然
该树是一个小顶堆
- 先加入的是边权大的边，最后加入的是较小的边，较大的边所表示的结点的父亲节点是较小的边

那么这就导出了另一条神奇的性质： $LCA(u,v)$ 为 $u,v$ 结点路径上的最小边权结点。所以我们就可以依靠这条性质，使用倍增， $Tarjan$ 或树链剖分等各种各样的算法求 $LCA$ 来统计答案了。这就是 $Kruskal$ 重构树。

顺便给一道板子题：BZOJ 3732: Network。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN=2e4+5;

const int MAXM=5e4+5;

int n,m,f[MAXN],a[MAXN],fa[MAXN],son[MAXN],sz[MAXN],dep[MAXN],st[MAXN];

int cnt,top[MAXN],to[MAXN<<1],nex[MAXN<<1];

struct Edge

{

    int u,v,d;

    bool operator < (const Edge& sjf) const {return d>sjf.d;}

}edge[MAXM];

inline int read()

{

    int re=0;

    char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();

    return re;

}

inline void add_edge(int x,int y)

{

    to[++cnt]=y,nex[cnt]=top[x],top[x]=cnt;

    to[++cnt]=x,nex[cnt]=top[y],top[y]=cnt;

}

inline int fd(int x)

{

    int r=x;

    while(f[r]!=r) r=f[r];

    int i=x,j;

    while(i!=r) j=f[i],f[i]=r,i=j;

    return r;

}

void dfs1(int now)

{

    for(int i=top[now];i;i=nex[i])

    {

        if(to[i]==fa[now]) continue;

        fa[to[i]]=now,dep[to[i]]=dep[now]+1,sz[to[i]]=1;

        dfs1(to[i]);

        sz[now]+=sz[to[i]];

        if(sz[to[i]]>sz[son[now]]) son[now]=to[i];

    }

}

void dfs2(int now,int line_top)

{

    st[now]=line_top;

    if(!son[now]) return ;

    dfs2(son[now],line_top);

    for(int i=top[now];i;i=nex[i])

    {

        if(to[i]==son[now]||to[i]==fa[now]) continue;

        dfs2(to[i],to[i]);

    }

}

int main()

{

    n=read(),m=read();

    for(int i=0;i<m;i++) edge[i].u=read(),edge[i].v=read(),edge[i].d=read();

    sort(edge,edge+m);

    for(int i=1;i<=n;i++) f[i]=i;

    for(int i=0;i<m;i++)

    {

        int fx=fd(edge[i].u),fy=fd(edge[i].v);

        if(fx!=fy)

        {

            a[++n]=edge[i].d;

            f[fx]=f[fy]=f[n]=n;

            add_edge(fx,n),add_edge(fy,n);

        }

    }

    for(int i=1;i<=n;i++)

        if(f[i]==i)

        {

            fa[i]=n,sz[i]=dep[i]=1;

            dfs1(i);

            dfs2(i,i);

        }

    m=read();

    while(m--)

    {

        int x=read(),y=read();

        if(fd(x)!=fd(y)) puts("-1");

        else

        {

            while(st[x]!=st[y])

            {

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

                x=fa[st[x]];

            }

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

            printf("%d\n",a[x]);

        }

    }

    return 0;

}

巴特西

Luogu P1967 货车运输(Kruskal重构树)

题面