RainAir
My OI Blog
RainAir

最短路
文章归档

「BZOJ5415」「NOI2018」归程

题目链接 题解 首先我们尝试把不能被车经过的边删掉,得到了一张新图。这个新图上每一个连通块的答案都相同。 所以 Dijkstra 是首先要跑的。然后我们发现如果可以离线的话我们可以把边和询问放在一起排序,用普通的并查集维护一下每个连通块到 $1$ 节点的最短距离就…

   378   2019-02-07 去围观

「NOIP2016」换教室

这道题甚至不如 T2 难...放在 T3 真的合适吗... 题目链接 题目描述 一张无向带权图,需要选择 $ N $ 次。每次在两个点 $ c_i,d_i $ 中,有 $ p_i $ 的概率选择点 $ d_i $,有 $ 1-p_i $ 的概率选择点 $ c_i $ ,每次选择相互独立。至多能选 $ M $ 次 $ d $ 类节点现…

   389   2018-08-17 去围观

「NOIP2017」逛公园

题意描述 给定一张无向图,定义 $ S $ 为 $ 1 $ 到 $ N $ 的最短路,求该无向图 $ 1 $ 到 $ N $ 的路径中长度小于等于 $ S+K $ 的方案。 题目链接 推荐大家去 uoj 多交一些题目,上面有很多 hack 数据。(像我之前认为 dij 就是 spfa+priority_queue)。 解题报…

   323   2018-08-03 去围观

「HNOI2009」最小圈

题目描述 题目分析 典型的01分数规划题目。 用来处理求平均值最小类的问题。 我们根据简单的转换,可以得出答案ans是可以二分的。 二分一个答案ans,我们把每个边权都减掉ans,再跑最短路,如果找到了一个负权环,那么说明ans不是最优。 最后:提醒大家注意精度…

   286   2018-03-17 去围观

分层图最短路

定义 分层图最短路问题,一般是指我们在可以进行分层的图上进行最短路。 一般模型是: 在图上,有k次机会可以直接通过一条边,问起点与终点之间的最短路径。 题目链接 分析 其实这一题我们用动态规划的思想看,用dist[i][k]表示免费了k次的最短路径 详细的转移请参…

   386   2018-03-11 去围观
标签
近期评论