昨天狐狸大大交流~~会了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:
分享到:
相关推荐
POJ3259--Wormholes,使用bellman方法。
北大POJ3259-Wormholes【Bellman】 解题报告+AC代码
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ1860-Currency Exchange【Bellman】 解题报告+AC代码
poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客
poj 5346题,四则运算表达式求值的实现,用栈和队列实现中缀转后缀后计算,含解题报告与源码
poj 1028 Web Navigation 的代码,已通过!
POJ 2151 Check the difficulty of problems. Practice for dynamic planning.
西北工业大学-c语言-POJ-题目及答案-第七季.doc
POJ - 2136. VerticalHistogram(统计字母个数)题目链接题目就是给你四行字符串,然后要你统计大写字母(只有大写字母)的个数,然后以特定
poj的结题报告,里面有一些详细的说明。poj的结题报告,里面有一些详细的说明
POJ 1170 动态规划。欢迎各种交流讨论。
POJ 北大在线代码判断,参考答案请参考
POJ-3299解题 C++源代码 Description Adapted from Wikipedia, the free encyclopedia The humidex is a measurement used by Canadian meteorologists to reflect the combined effect of heat and humidity. It...