c语言sscanf函数的用法是什么
326
2022-08-25
POJ-1511 初探Bellman-Ford,再水SPFA模板题..
昨天狐狸大大交流~~会了bellman-ford..
bellman-ford简单概括就是: /* d [ i ] 来记录源点到 i 点的最小距离,初始值源点的 d [ ] 为0,其他的点为一个足够大的数 line[ ] .start 表示线段的起点, line[ ] .end 表示线段的终点, line[ ] .w 表示线段的权值, */ for ( times=1 to NumOfPoint ) for ( i = 1 to NumOfLine ) relax ( line[ i ] ) 其核心就在 ralex , relax { d [ line[i].end ] = min ( d [ line[i].end ] , d [ line[i].start ] + line[ i ] .w ) }
思想有点类似kruscal..但其每次都是扫描所有的边...写的话..5行之内搞定...但是有tick就是如果题目没有强调...要判断有没有负环...有负环的话那么是无解的..因为可以无限爱负环上转圈而使得值无限的小...
SPFA是在bellman-ford上的改进...因为bellman-ford每次都要扫描所有的边..这是很浪费的..因为大部分的边并没有更新..SPFA则用一个队列 ( 其实也没必要是队列..甚至是个无序的集合都行,目的是标记当前更新过但还未拓展的点 ) 优化...
这个过程用一个bool数组来维护...入队时标记为true..出队之前对其有更新就入不了队...当出队时..则讲其又还原为false..那么后面如果又更新到了...还能入队..)
介于每次都是更新时扫面的是某点为起点的所有线段...那自然想到用前向星的方式来存储边最方便...即省了空间又高度符合所要做的操作...
POJ1151 题目的意思抽象出来就是给一个有向图..求 1到所有点的最小距离之和与所有点到1最小距离之和相加的最小值....用一个正向的原图做一次SPFS..再将所有边反过来做一次SPFS..轻轻松松鸭梨不大.....
Program:
#include
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~