| 题目名称 | 1439. [NOIP 2013]货车运输 |
|---|---|
| 输入输出 | truck.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 20 |
| 题目来源 |
 超级傲娇的AC酱
于2013-11-18加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：552， 提交：1480， 通过率：37.3% | ||||
 +1s |
100 | 0.011 s | 1.10 MiB | C++ |
 AntiLeaf |
100 | 0.012 s | 0.69 MiB | C++ |
|
+1s |
100 | 0.018 s | 1.10 MiB | C++ |
|
+1s |
100 | 0.026 s | 1.10 MiB | C++ |
 _Itachi |
100 | 0.034 s | 1.09 MiB | C++ |
 Tiny |
100 | 0.035 s | 41.99 MiB | C++ |
 new ioer |
100 | 0.036 s | 23.56 MiB | C++ |
 Youngsc |
100 | 0.043 s | 1.50 MiB | C++ |
 shallwe |
100 | 0.043 s | 5.43 MiB | C++ |
|
AntiLeaf |
100 | 0.046 s | 0.69 MiB | C++ |
| 本题关联比赛 | |||
| 2019级快乐小组模拟赛19.9.19 | |||
| 中秋节快乐！ | |||
| 关于 货车运输 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
唐丸了，写了没交
| ||||
|
自己写的Kruskal+Tarjan超时了......
 增强型图元文件
2021-09-24 19:28
54楼
| ||||
|
| ||||
|
构造倍增数组的时候运算顺序出错卡了一上午.挂起来引以为戒.
| ||||
|
终于用树链剖分和稀疏表AC了这道题。(>﹏<)
| ||||
|
敲错一个字母结果两个A折磨我半天。。。
| ||||
|
4 3
1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3  胡嘉兴
2017-10-27 09:30
49楼
| ||||
|
新人求助，火车运输那题，本机AC提交RE。。
| ||||
|
倍增写劣了啊..跳到同一深度的时候把x和y搞混了...
调试了一下午+一晚上.. 中午来机房终于A了.. | ||||
|
启发式合并
| ||||
健康铀
leon
snake
WHZ0325
...
Ays
>.<【题目描述】
$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$。
【样例输入】
4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3
【样例输出】
3 -1 3
【数据规模与约定】
对于 $30$% 的数据，$1≤n<1000，1≤m<10,000，1≤q<1000$；
对于 $60$% 的数据，$1≤n<1000，1≤m<5×10^4，1≤q<1000$；
对于 $100$% 的数据，$1≤n<10^4，1≤m<5×10^4，1≤q<3×10^4，0≤z≤10^5$。
【来源】
NOIP2013 Day1 Task3