搜索与图论
1s 可以执行指令10^7~10^8次
dp问题是没有环的最短路问题。最短问题一般不用dp,dp时间复杂度低,最短路问题时间复杂度高。
最短路问题只有所有边权都为1,才用bfs。
spfa可以看有无负环,spfa用的很多
其中,dijkstra朴素版需要特别注意重边,bellman-ford和floyd需要注意最后判断的是0x3f3f3f3f/2(INF/2)
spfa用的是queue,优化dijkstra用的是优先队列,bellan-ford、floyd啥都没用
floyd记得初始化d[i][i]
SPFA可以处理负权边,但是不能处理有负权回路的图;而Dijkstra不能处理带有负权边和负权回路的图,因为Dijkstra算法在计算最短路径时,不会因为负边的出现而更新已经计算过(收录过)的顶点的路径长度;
总结一下:Bellman-ford可以处理任意带负权边和负权环的图,SPFA可以处理带负权边的图,Dijkstra只能处理带正权边的图;当然,从时间复杂度的效率来讲,是反过来的,hh
m和n^2一个级别是稠密图,m和n一个级别是稀疏图。
memset这个函数的作用是将数字以单个字节逐个拷贝的方式放到指定的内存中去。
这样你可能以为如果你赋值1的话会让整个dp数组里的每一个int变成1,其实不然。
memset(dp,1,sizeof(dp));
以上代码执行后,dp数组的内容为 00000001 00000001 00000001 00000001 转化为十进制后不为1
0x3f3f3f3f的十进制是1061109567,也就是10^9级别的(和0x7fffffff一个数量级),而一般场合下的数据都是小于10^9的,所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。
另一方面,由于一般的数据都不会大于10^9,所以当我们把无穷大加上一个数据时,它并不会溢出(这就满足了“无穷大加一个有穷的数依然是无穷大”),事实上0x3f3f3f3f+0x3f3f3f3f=2122219134,这非常大但却没有超过32-bit int(-2147483648~2147483647)的表示范围,所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。
最后,0x3f3f3f3f还能给我们带来一个意想不到的额外好处:如果我们想要将某个数组清零,我们通常会使用memset(a,0,sizeof(a))这样的代码来实现(方便而高效),但是当我们想将某个数组全部赋值为无穷大时(例如解决图论问题时邻接矩阵的初始化),就不能使用memset函数而得自己写循环了(写这些不重要的代码真的很痛苦),我们知道这是因为memset是按字节操作的,它能够对数组清零是因为0的每个字节都是0,现在好了,如果我们将无穷大设为0x3f3f3f3f,那么奇迹就发生了,0x3f3f3f3f的每个字节都是0x3f!所以要把一段内存全部置为无穷大,我们只需要memset(a,0x3f,sizeof(a))。
最小生成树