RainAir
My OI Blog
RainAir

最小生成树
文章归档

次小生成树

题目链接 题目描述 给定一张图,求出它的严格次小生成树。 解题报告 预备知识:最小生成树,最近公共祖先 我们首先来考虑一下严格最小生成树和不严格次小生成树的区别。 首先,对于一个图,可能不只有一个最小生成树。 那么,不严格次小生成树,只需要找出不…

   335   2018-07-13 去围观

多次询问的最长瓶颈路

题目链接 题目大意 给出一个由 $ n $个点 $ m $条边的图,现有$ q $组询问,每次需要你求出从$ x $到$ y $的一条简单路径,使路径上所有边中最小值最大,并输出这个最大值。 若不存在这样的路径,则输出$ −1 $。 解题报告 做这一道题之前,建议先看一下单次询问…

   296   2018-07-10 去围观

单次询问的最长瓶颈路

题目链接 题目大意 给定一个图,求瓶颈最短路(及求出一条是该路径最大值最小的路径)。 解题报告 方法一 注意最大值最小,我们立马想到了二分。 实际上,由于这道题拥挤度的范围不大,可以二分。 二分的区间就在边权最小值与最大值之间。 我们使用bfs来检查…

   328   2018-07-08 去围观

「NOIP2013」货车运输

题目描述 A 国有n座城市,编号从1到n,城市之间有m条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有q辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。 数据范围 对于30%的数据,$ 0 < n < 1000,0 < m …

   310   2018-04-14 去围观
标签
近期评论