poj2488--回溯
摘要: 简单说一下回溯法，回溯跟深度优先遍历是分不开的，我们倾向于把回溯看做深度优先遍历的延伸。我们知道，图的深度优先遍历每个节点只会被访问一次，因为我们一旦走过一个点，我们就会做相应的标记，避免重复经过同一个点。而回溯的做法是，当走过某一个点时，标记走过，并把该点压栈；当该节点出栈时，我们再把它标记为没有走过，这样就能保证另外一条路也能经过该点了
阅读全文
posted @
2012-08-20 16:09 小鼠标 阅读(433) |
评论 (0) 编辑
poj2386--图的遍历
摘要: 图的常见遍历方式有两种：深度优先遍历和广度优先遍历，他们的作用是将图中的每个点都访问一遍，只不过是顺序不同。
如果把图中的每条边长都相等（比如都是1）的话，深度优先遍历的过程是：
1.任意选定一个点p0作为遍历的起点
2.从未访问节点中任选一个距离p0最近的点进行访问，并标记该点被访问过
3.重复第2步，直到该连通分支中的所有节点都被访问过
阅读全文
posted @
2012-08-20 12:23 小鼠标 阅读(1592) |
评论 (0) 编辑
zoj1060，poj1094--拓扑排序
摘要: 下面我先说以下拓扑排序：
严蔚敏《数据结构》上的定义是：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
直观的说偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。
拓扑排序的具体做法是：
1.在有向图中选择一个没有前驱（入度为0）的顶点，输出
2.从图中删除该顶点和所有以它为尾的弧，并更新相关点的入度
3.重复1，2步，直到所有顶点都被输出，或者发现图中存在回路。
阅读全文
posted @
2012-08-16 19:19 小鼠标 阅读(1795) |
评论 (0) 编辑
zoj2971--英文转换为数字
摘要: 题意描述：
我们知道英语描述数字与汉语是不同的，题目要求给出英文描述的数字，输出实际的数字。
解题思路是，把所有关键字分成两类，一类是“数字”，另一类是“权重”，遇到数字就加上去，遇到权重就乘上去，最后输出结果就是了。不过这样还不行，因为这会导致权重累计相乘，比如前面有一个million，要乘1000 000，后面又有一个thousand，还要乘1000，这显然是不对的……
阅读全文
posted @
2012-08-12 09:18 小鼠标 阅读(1193) |
评论 (0) 编辑
单源最短路径Dijkstra算法
摘要: dijkstra算法是解决单源最短路径问题的经典算法，具有O(N^2)的时间复杂度（N为节点个数），这种算法采用的是贪心策略，它与最小生成树的Prim算法极其相似，这两种算法仅仅是cost[]代表的含义不同……
阅读全文
posted @
2012-08-08 16:27 小鼠标 阅读(1869) |
评论 (0) 编辑
memset()和sizeof()
摘要: 数组初始化的时候常用for()循环，不过如果考虑效率的话，最好用memset()，下面简单介绍以下memset()。
函数原型：
void *memset(void *s, int ch, size_t n)
函数解释：将s中前n个字节替换为ch并返回s；
……
sizeof是C/C++中的一个操作符（operator），而不是函数……
阅读全文
posted @
2012-08-07 23:38 小鼠标 阅读(3174) |
评论 (2) 编辑