P1967

[NOIP 2013 提高组] 货车运输

题目背景

NOIP2013 提高组 D1T3

题目描述

A 国有 $n$ 座城市，编号从 $1$ 到 $n$ ，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

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

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

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

接下来 $q$ 行，每行两个整数 $x,y$ ，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x \neq y$ 。

输出格式

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

输入输出样例

输入样例 #1

输出样例 #1

3
-1
3

说明/提示

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

对于 $60\%$ 的数据， $1 \le n < 1000$ ， $1 \le m < 5\times 10^4$ ， $1 \le q< 1000$ ；

对于 $100\%$ 的数据， $1 \le n < 10^4$ ， $1 \le m < 5\times 10^4$ ， $1 \le q< 3\times 10^4$ ， $0 \le z \le 10^5$ 。

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P1967 [NOIP 2013 提高组] 货车运输题解 Author: Yuyi 题意分析题意是要我们求：在 $x$ 到 $y$ 的所有连通路径中，单条边权的最小值尽可能大。如果两人压根不连通，输出 1 。我们之前已经解决过“U92652 Kruskal重构树模板”和“P4768 归程”，这题和它们如出一辙，只不过把“求最小”变成了“求最大”而已…

点击展开完整题解点击收起题解

2026年8月9日 22:32

P1967 [NOIP 2013 提高组] 货车运输题解

Author: Yuyi

题意分析

题意是要我们求：在 $x$ 到 $y$ 的所有连通路径中，单条边权的最小值尽可能大。如果两人压根不连通，输出 -1。我们之前已经解决过“U92652 Kruskal重构树模板”和“P4768 归程”，这题和它们如出一辙，只不过把“求最小”变成了“求最大”而已。可以说是标准的最大生成树 + Kruskal 重构树的练手题。

正解推导过程

最大生成树：因为货车要在不超重的情况下尽可能运更重的货物，所以应该优先走限重最大的路。我们将所有的边按限重**从大到小（降序）**排列。
Kruskal 重构树：
- 遍历降序排好的边，如果边的两个端点 $u$ 和 $v$ 不在同一个并查集里，就创建一个新的虚拟节点 tot。
- 把 tot 的点权 val 赋值为这条边的限重 $z$ 。
- 让 tot 作为 $u$ 和 $v$ 所在集合的根节点的父亲（即 $u, v$ 是 tot 的左右儿子）。
转化为 LCA 问题：
- 由于我们是按边权降序建树，所以建出来的 Kruskal 重构树是一个“小根堆”结构（越靠近树根的点权越小，越靠近叶子的点权越大）。
- 这意味着，两个节点 $x$ 和 $y$ 想要连通，它们在重构树上必然要走到它们的最近公共祖先 (LCA) 才能跨越过去。
- 而这个 LCA 的点权，恰好就是 $x$ 到 $y$ 路径上最大的“瓶颈边”（也就是题目要求的最大载重）！
在线查询：面对 $q$ 次询问，先用并查集的 find 判断是否连通（不连通输出 -1）；若连通，直接跑倍增求出 LCA，输出 val[lca] 即可。

正解代码及分析

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 20005; // 图最多 10000 个点，重构树最多 2N-1，开到两万
const int maxm = 50005; // 边数最多 50000
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n,m;
struct Edge
{
    int u,v,w;
}e[maxm];
bool cmp(Edge A,Edge B)
{
    return A.w > B.w; // 找最大瓶颈，所以按载重降序排列
}
int fa[maxn];
int find(int u)
{
    if(u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}
int val[maxn],ch[maxn][2],dep_node[maxn],f[maxn][20];
void dfs(int u,int father)
{
    dep_node[u] = dep_node[father] + 1;
    f[u][0] = father;
    rep(i,1,19) f[u][i] = f[f[u][i-1]][i-1];
    if(ch[u][0]) dfs(ch[u][0],u);
    if(ch[u][1]) dfs(ch[u][1],u);
}
int lca(int x,int y)
{
    if(dep_node[x] < dep_node[y]) swap(x,y);
    dep(i,19,0) // 为防止和上面宏定义的 dep 冲突，这里数组改名为 dep_node
    {
        if(dep_node[f[x][i]] >= dep_node[y]) x = f[x][i];
    }
    if(x == y) return x;
    dep(i,19,0)
    {
        if(f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
void solve()
{
    read(n),read(m);
    rep(i,1,m) read(e[i].u),read(e[i].v),read(e[i].w);
    sort(e+1,e+1+m,cmp);
    rep(i,1,n*2) fa[i] = i,ch[i][0] = ch[i][1] = 0;
    int tot = n;
    rep(i,1,m)
    {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv)
        {
            tot++;
            val[tot] = e[i].w;
            ch[tot][0] = fu;
            ch[tot][1] = fv;
            fa[fu] = tot;
            fa[fv] = tot;
        }
    }
    rep(i,1,tot)
    {
        if(fa[i] == i) dfs(i,0); // 从每棵树的树根向下跑 DFS
    }
    int q;
    read(q);
    while(q--)
    {
        int u,v;
        read(u),read(v);
        if(find(u) != find(v)) cout << -1 << '\n'; // 询问次数达到 3万，稳妥起见依然换用 \n 防止 TLE
        else cout << val[lca(u,v)] << '\n';
    }
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：Kruskal 排序和建重构树为 $O(M \log M)$ ；重构树 DFS 预处理为 $O(N \log N)$ ；最后的 $Q$ 次在线倍增 LCA 查询为 $O(Q \log N)$ 。总体时间复杂度约为 $O(M \log M + Q \log N)$ 。在此题中规模最高才区区数万，跑起来耗时以毫秒计，绝对是降维打击般的解法。
空间复杂度：原图节点不超过一万个，按规范重构树节点规模开至 maxn = 20005 齐平，边数 maxm = 50005。其中最占空间的也就只有一个存倍增状态的 f 数组（ $20005 \times 20 \times 4$ Byte 大约 1.5MB），空间复杂度 $O(N \log N)$ ，极为极致。

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。