ZhYic

A vegetable chicken

Spfa最短路模板

Spfa的写法 bfs正规spfa (code) 区别 bfs是将目前搜到的点所连的边加入搜索队列,堆优化后每次取最短的边进行松弛,dfs需要一回走到底,每条分支都进行更新,相当于剪枝搜索。因此dfs对于每个点需要多次更新,时间复杂度远大于bfs。策略:dfs是剪枝暴搜,如果顺当前道路走到当前点p,费用大于到p的最短路,那么以此更新p后所有点必然大于原最短路径。bfs是纯正dp思想,贝尔曼福德的改进版。适用:dfs适用于边少......

树状数组模板

(code)解释如下: 来源:百度图片搜索(img)树状数组每个节点所存的值都有不同含义,具体意义则为C[i]=A[i]+A[i-1]+....+A[i-2^k+1](k表示i的二进制末尾连续0的个数); 举个粟子......

洛谷OJP1222三角形题解

这道题已经有一位巨神发了汤普森积分的解法了,而且我的解法并不是最优的,仅供参考。 首先,计算几何中一种非常常用的算法是扫描线算法(这是一篇比较全面的博文),但是与矩形中的扫描线算法不同,三角形因为边不是都与坐标轴平行,故不能采用矩形面积计算中常用的差分+线段树维护 回顾一下扫描线算法的思想(quote)......于是我们可以想到,仿照类似于矩形面

洛谷OJP1016旅行家的预算题解

看了一下各位大佬的题解,感觉代码有些长,这里介绍一下~~简短的~~简陋的方法(不涉及单调队列,完全按照题面意思的贪心+模拟)思路 首先将起点和终点与道路上的加油站视为等价节点,按照距离起点的距离(即为通过顺序)排序。然后对于每一个节点我们可以进行以下贪心策略 - 如果可以直达下一个油价更低的节点就加满够到此节点的油,开过去(中间的不用管) - 如果不能直达就加满油(因为中转节点的油更贵要少加),开到能到范围内油价最低的加油站[1] 对于[1]的证明: 因为从A到B的路

page: 1

...


© 2018 ZhongYic00