RainAir
My OI Blog
RainAir

最短路
文章归档

JZOJ 2019.10.30模拟赛总结

赛时 T1 是个带环的博弈,我比较菜不会做 写了无环和有自环的点就跑了。 T2 这种题一看就很 $O(n^2)$ 可是我只会暴力 就跑了 $n$ 遍最短路,拿到了一点点暴力分 T3 一开始不会,发现 Sub1 可做 Sub2 可做 Sub5 可做。。。写了一场然后发现 Sub5 套个cdq 就过了,可惜…

   45   2019-11-02   45 去吊打作者

「BZOJ5415」「NOI2018」归程

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

   423   2019-02-07   423 去吊打作者

「NOIP2016」换教室

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

   445   2018-08-17   445 去吊打作者

「NOIP2017」逛公园

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

   381   2018-08-03   381 去吊打作者

「HNOI2009」最小圈

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

   353   2018-03-17   353 去吊打作者

分层图最短路

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

   449   2018-03-11   449 去吊打作者
标签
近期评论