- 浏览: 316903 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
首先献上模板:【点都是默认为从1到n编号,用dijk和floyd时要注意重边】
①DIJK
#define inf 0x3fffffff #define M 105 int dist[M], map[M][M], n; bool mark[M]; void init () { int i, j; for (i = 1; i <= n; i++) //i==j的时候也可以初始化为0,只是有时候不合适 for (j = 1; j <= n; j++) map[i][j] = inf; } void dijk (int u) { int i, j, mins, v; for (i = 1; i <= n; i++) { dist[i] = map[u][i]; mark[i] = false; } mark[u] = true; dist[u] = 0; //既然上面的map当i==j时不是0,就要这句 while (1) { mins = inf; for (j = 1; j <= n; j++) if (!mark[j] && dist[j] < mins) mins = dist[j], v = j; if (mins == inf) break; mark[v] = true; for (j = 1; j <= n; j++) if (!mark[j] && dist[v] + map[v][j] < dist[j]) dist[j] = dist[v] + map[v][j]; } }
②Floyd
#define inf 0x3fffffff //注意,太大会溢出 #define M //最大点数 int n, dist[M][M]; //n:实际点数 void init () //有时候需要初始化 { int i, j; for (i = 1; i <= n; i++) for (j = i + 1; j <= n; j++) dist[i][j] = dist[j][i] = inf; } void floyd () { int i, j, k; for (k = 1; k <= n; k++) for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) //有的题目会溢出就要自己变通了 if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; }
③vector后插的SPFA
#define inf 0x3fffffff #define M 105 //最大点数 struct son{ int v, w; }; vector<son> g[M]; bool inq[M]; //入队列标记 int dist[M], n; //n:实际点数 void init () { for (int i = 1; i <= n; i++) g[i].clear(); } void spfa (int u) { int i, v, w; for (i = 1; i <= n; i++) { dist[i] = inf; inq[i] = false; } queue<int> q; q.push (u); inq[u] = true; dist[u] = 0; while (!q.empty()) { u = q.front(); q.pop(); inq[u] = false; for (i = 0; i < g[u].size(); i++) { v = g[u][i].v; w = g[u][i].w; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (!inq[v]) { q.push (v); inq[v] = true; } } } } }
④模拟前插的SPFA(多数情况下比③快,数据较为复杂就会看出来)
#define inf 0x3fffffff #define M 1005 //最大点数 struct edge{ int v, w, next; }e[10005]; //估计好有多少条边 int pre[M], cnt, dist[M], n; bool inq[M]; //注意初始化 void init () { cnt = 0; memset (pre, -1, sizeof(pre)); } //注意双向加边 void addedge (int u, int v, int w) //加边函数,慢慢模拟就会明白的 { e[cnt].v = v; e[cnt].w = w; e[cnt].next = pre[u]; //接替已有边 pre[u] = cnt++; //自己前插成为u派生的第一条边 } void spfa (int u) { int v, w, i; for (i = 1; i <= n; i++) //对于从1到n的编号 dist[i] = inf, inq[i] = false; dist[u] = 0; queue<int> q; q.push (u); inq[u] = true; while (!q.empty()) { u = q.front(); q.pop(); inq[u] = false; for (i = pre[u]; i != -1; i = e[i].next) { w = e[i].w; v = e[i].v; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (!inq[v]) { q.push (v); inq[v] = true; } } } } }
第一题:http://acm.hdu.edu.cn/showproblem.php?pid=2544
灰常水,floyd、dijk、spfa都可以
第二题:http://acm.hdu.edu.cn/showproblem.php?pid=2066
简单题,多源多终点,spfa、dijk都很快解决
第三题:http://acm.hdu.edu.cn/showproblem.php?pid=2112
用STL的map把地名映射到编号就可以套模板了,注意路是双向的就行了
第四题:http://acm.hdu.edu.cn/showproblem.php?pid=1874
和第一题一样的水
第五题:http://acm.hdu.edu.cn/showproblem.php?pid=1142
最短路+记忆化搜索
详情:http://972169909-qq-com.iteye.com/blog/1149589
第六题:http://acm.hdu.edu.cn/showproblem.php?pid=1385
floyd记忆路径
详情:http://972169909-qq-com.iteye.com/blog/1150803
第七题:http://acm.hdu.edu.cn/showproblem.php?pid=1548
水题,构图后直接dijk或spfa就可以了
第八题:http://acm.hdu.edu.cn/showproblem.php?pid=1217
floyd的灵活运用
详情:http://972169909-qq-com.iteye.com/blog/1149095
第九题:http://acm.hdu.edu.cn/showproblem.php?pid=2680
简单题,多起点单终点,反过来dijk或者spfa就可以了,注意路是单向的,所有路都要反过来,逆向思维
第十题:http://acm.hdu.edu.cn/showproblem.php?pid=2923
题目意思可能比较难懂,而且有重边,floyd
详情:http://972169909-qq-com.iteye.com/blog/1150818
第十一题:http://acm.hdu.edu.cn/showproblem.php?pid=2962
直接枚举或二分枚举+最短路
详情:http://972169909-qq-com.iteye.com/blog/1159652
第十二题:http://acm.hdu.edu.cn/showproblem.php?pid=2722
这题主要是构图麻烦,会用sscanf就比较好做了,构好图之后就是水题了
第十三题:http://acm.hdu.edu.cn/showproblem.php?pid=1690
暴力构图,枚举2点间距离,根据表格定好花费,然后直接floyd就可以了【注意数太大要用64位,无穷大定为-1比较好处理】
第十四题表示压力好大……
第十五题:http://acm.hdu.edu.cn/showproblem.php?pid=1596
floyd水题
第十六题:http://acm.hdu.edu.cn/showproblem.php?pid=1598
并查集+贪心 或 二分枚举+最短路
详情:http://972169909-qq-com.iteye.com/blog/1159593
第十七题表示不想做……
第十八题:http://acm.hdu.edu.cn/showproblem.php?pid=2363
枚举高度差+最短路,比较容易错
详情:http://972169909-qq-com.iteye.com/blog/1159650
第十九题表示很蛋疼……
第二十题:http://acm.hdu.edu.cn/showproblem.php?pid=2833
一题比较难的记忆化搜索+最短路【或dp+最短路】
详情:http://972169909-qq-com.iteye.com/blog/1159661
发表评论
-
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2688KIDx的解题报告 题 ... -
LOJ 1009 Back to Underworld
2012-01-10 16:50 0KIDx 的解题报告 题目链接:http://ligh ... -
【floyd的灵活运用】LOJ 1174 Commandos
2012-01-10 15:02 1467KIDx的解题报告 题目链接:http://light ... -
HDU 1728 逃离迷宫 + HDU 1072 Nightmare
2011-11-08 18:40 7496KIDx 的解题报告 HDU 1728 逃离迷宫 http:/ ... -
【差分约束(spfa版)】总结
2011-10-05 21:02 7102KIDx 的解题报告 先总结下: 第一: 感觉难点在于建 ... -
【完美匹配-KM算法】HDU总结
2011-10-02 14:35 7198KIDx 的解题报告 题目链接:http://acm.hdu. ... -
【记忆化搜索+最短路】HDU 2833 WuKong
2011-08-28 09:49 2539http://acm.hdu.edu.cn/showprobl ... -
【最短路+枚举】HDU 2962 Trucking【2012-1-20更新】
2011-08-28 09:17 1841KIDx 的解题报告 题目链接:http://acm.hd ... -
【枚举+最短路】HDU 2363 Cycling
2011-08-28 09:07 1804http://acm.hdu.edu.cn/showprobl ... -
【并查集+贪心(或)最短路+二分枚举】HDU 1598
2011-08-27 23:25 4079http://acm.hdu.edu.cn/showprobl ... -
【HDU、二分匹配、最大匹配/新增1005+1008代码】总结
2011-08-22 14:19 1556KIDx 的解题报告 给出基本定义: 第一题:hdu ... -
【floyd/要防重边】HDU 2923 Einbahnstrasse
2011-08-16 21:48 2343http://acm.hdu.edu.cn/showprobl ... -
【floyd记录路径】HDU 1385 Minimum Transport Cost
2011-08-16 21:26 1970http://acm.hdu.edu.cn/showprobl ... -
【最短路spfa+记忆化搜索】HDU 1142 A Walk Through the Forest
2011-08-15 15:21 2211http://acm.hdu.edu.cn/showprobl ... -
【floyd神器】HDU 1217 Arbitrage
2011-08-14 22:09 1788http://acm.hdu.edu.cn/showprobl ... -
【次小生成树】POJ 1679 The Unique MST
2011-08-12 10:00 1042http://poj.org/problem?id=1679 ... -
【拓扑排序】HDU 2647 Reward【2012/3/25更新】
2011-08-11 19:26 1938http://acm.hdu.edu.cn/showprobl ... -
【拓扑排序】HDU 1285 确定比赛名次
2011-08-10 21:38 1168http://acm.hdu.edu.cn/showprobl ... -
【二进制状态压缩+子集枚举/新增深搜】HDU 1557 权利指数
2011-07-28 11:23 2041http://acm.hdu.edu.cn/showprobl ... -
HDU 1175 连连看【2011年11月14号更新】
2011-06-02 17:00 1709http://acm.hdu.edu.cn/showprobl ...
相关推荐
--SPFA(最短路快速算法) // thanks to love8909 几何相关 --初等几何学 --多边形几何 --几种凸包算法 --半平面交算法 --旋转卡壳算法 数据结构 --可合并堆(左偏树实现) --树状数组 --Trie树 //thanks to love8909 ...
做ACM最短路问题普遍算法的Floyd-Dijkstra-Spfa板子..
1. **初始化**:设置起点到所有顶点的距离为无穷大,起点到自身的距离为0。创建一个队列,将起点加入队列,并标记起点为已入队状态。 2. **循环处理队列中的顶点**: - 取出队列头部的顶点。 - 对于该顶点的所有...
spfa模板,双向图的,但是里面也有介绍改成单向图的。 实际是freepascal的,但是没有分类,只好放到C/C++分类里了,希望能帮到大家
图论--最短路--第K短路(IDA*)(IDA Star)模板 传递闭包: 传递闭包 欧拉与哈密尔顿路径: 欧拉回路 图论--欧拉回路--弗罗莱算法模板 LCA: 图论--LCA--Tarjan(离线) 图论--LCA--树上...
### SPFA算法详解 #### 一、算法简介 SPFA(Shortest Path Faster Algorithm)算法是一种高效的单源最短路径算法。它由西南交通大学的段凡丁教授在1994年提出。与传统的最短路径算法如Dijkstra算法相比,SPFA在...
同时,对于这些经典算法的变种和扩展,如Floyd-Warshall算法(用于求所有节点对之间的最短路径)和Johnson's Algorithm(处理大规模负权图的最短路问题),也要有所了解,以便在面对更复杂问题时能灵活应对。...
1. 初始化:将源点的所有路径长度设为0,其他顶点的路径长度设为无穷大。 2. 迭代:对图中的每一条边进行V-1次松弛操作(V为图中顶点的数量)。每次迭代中,如果找到一条更短的路径,就更新目标顶点的路径长度。 3. ...
总结来说,SPFA算法是求解带负权边图的最短路径的一种高效方法,虽然在最坏情况下可能不如Bellman-Ford算法稳定,但通常在实践中表现出更好的性能。理解这两种算法的原理和实现细节对于解决图论问题和参加编程竞赛都...
3. **初始化**:开始时,将源点的距离设置为0,其他所有顶点的距离设置为无穷大,表示未发现的路径。 4. **核心循环**:进入主循环,每次从队列中取出一个顶点`u`,遍历与其相邻的所有顶点`v`,如果通过边`(u, v)`...
队列优化的Bellman-Ford最短路算法(SPFA,Shortest Path Faster Algorithm)是一种在图论中用于寻找有向图中单源最短路径的算法,它是在经典Bellman-Ford算法基础上进行优化得到的。Bellman-Ford算法本身能够处理...
最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。
最短路算法进阶(链式前向星+堆优化+SPFA) 本文主要介绍了最短路算法的进阶知识,包括链式前向星、堆优化和SPFA算法的应用。 一、链式前向星 链式前向星是一种存图方式,用于存储有向图中的边信息。这种存图方式...
STL实现的,看完了一定会懂了的。我就是看的这个呢亲
在提供的"最短路之SPFA算法.mht"文件中,很可能包含了关于SPFA算法的具体实现、例子以及分析。这个文件可能包含了用编程语言(如C++、Python等)实现的SPFA算法代码,以及通过实例来解释如何运用该算法求解最短路径...
SPFA(Shortest Path Faster Algorithm)是一种高效的单源最短路算法,广泛应用于图论和动态规划等领域。下面是对SPFA算法的详细介绍和优化。 基本实现 SPFA算法的基本思想是通过relax操作来更新节点的距离值。...
SPFA(Shortest Path Faster Algorithm)算法是一种用于解决图论中的单源最短路径问题的算法,它是贝尔曼-福特(Bellman-Ford)算法的一种优化版本,主要应用于求解带有负权重边的图的最短路径。SPFA通过使用队列...
相比于Bellman-Ford算法,SPFA在实践中通常更快,但其最坏情况下的时间复杂度仍为O(n^2)。SPFA对于稀疏图,即边的数量远小于节点数量的情况,表现良好。 链式前向星存图是一种常用的图存储结构,它使用邻接表而非...
1. 初始化:设置所有顶点到源点的距离为无穷大(除了源点自身距离为0),并将源点加入队列。 2. 循环处理:当队列不为空时,执行以下操作: - 取出队首元素u,遍历u的所有邻接点v。 - 计算新路径d' = d[u] + w(u,...
标题中的"SPFA.zip_SPFA"表明这是一个与SPFA算法相关的压缩文件,SPFA全称为Shortest Path Faster Algorithm,即最短路径更快算法。这是一种解决图论中的单源最短路径问题的算法,通常用于有向图。描述提到SPFA算法...