RainAir
My OI Blog
RainAir
「BZOJ 3669」「NOI2014」魔法森林

题目链接

题目简述

给定 $N$ 个点 $M$ 条边的无向图,每条边有两个权值 $a$ 与 $b$ 。求一条 $1$ 到 $n$ 的路径使得路径经过边的最大 $a$ 与最大 $b$ 的和最小。无法到达输出 $-1$。

$ n \leq 50000,m \leq 100000$。

解题报告

乱入:这个题目只需要枚举 a 然后动态加边跑 SPFA 就可以了。
请不要用一个时间复杂度是 $O(nm)$ 的算法来解决问题。
好我们开始正经的做题。
首先如果只有一个权值的话非常好做就是 $1$ 到 $n$ 的最小瓶颈生成树。但是两个权值怎么做呢?我们考虑对 $a$ 排序,枚举我们的答案 $a’$ ,每次加入满足 $a \leq a’$ 的边即可,如果构成了一个树我们就进行统计答案,如果加边的时候已经连通就贪心地删掉 $b_i$ 最大的边。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/405
如文中无特殊声明,本文采用 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

「BZOJ 3669」「NOI2014」魔法森林
题目链接 题目简述 给定 $N$ 个点 $M$ 条边的无向图,每条边有两个权值 $a$ 与 $b$ 。求一条 $1$ 到 $n$ 的路径使得路径经过边的最大 $a$ 与最大 $b$ 的和最小。无法到达输出 $-1$。 $…
扫描二维码继续阅读
2019-01-06
标签
近期评论