RainAir
My OI Blog
RainAir
「NOIP2013」货车运输

题目描述

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

数据范围

对于30%的数据,$ 0 < n < 1000,0 < m < 10000,0 < q< 1,000 $
对于60%的数据,$ 0 < n < 1000,0 < m < 50000,0 < q< 1,000 $
对于100%的数据,$ 0 < n < 10000,0 < m < 50000,0 < q < 30000,0 ≤ z ≤ 100,000 $

解题报告

这一题一看,发现很难。
(但是其实不难
冷静分析,发现我们可以用一个FLOYD的思想来写,但是这样只有30pts
好像还要优化…
100pts做法
我们其实只需要这个图的最大生成树即可,然后如果两个点联通,则它们连接的边就是答案,用倍增搞一下就行。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/19
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「NOIP2013」货车运输
题目描述 A 国有n座城市,编号从1到n,城市之间有m条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有q辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多…
扫描二维码继续阅读
2018-04-14
标签
近期评论