图论
hdu3549--网络流      摘要: 网络流算法描述如下:
1.利用残留网络寻找增广路
2.将这一条增广路在图中去除,并修改残留网络
3.重复1、2步,直到找不到残留网络   阅读全文
posted @ 2012-09-07 22:13 小鼠标 阅读(288) | 评论 (0)  编辑
poj1273--网络流      摘要: 最赤裸的网络流,不断找出增广路增广即可。找增广路时,这里用的深度优先搜索。  阅读全文
posted @ 2012-09-07 21:29 小鼠标 阅读(270) | 评论 (1)  编辑
hdu3118Arbiter
posted @ 2012-09-04 22:39 小鼠标 阅读(205) | 评论 (0)  编辑
poj2488--回溯      摘要: 简单说一下回溯法,回溯跟深度优先遍历是分不开的,我们倾向于把回溯看做深度优先遍历的延伸。我们知道,图的深度优先遍历每个节点只会被访问一次,因为我们一旦走过一个点,我们就会做相应的标记,避免重复经过同一个点。而回溯的做法是,当走过某一个点时,标记走过,并把该点压栈;当该节点出栈时,我们再把它标记为没有走过,这样就能保证另外一条路也能经过该点了  阅读全文
posted @ 2012-08-20 16:09 小鼠标 阅读(417) | 评论 (0)  编辑
poj2386--图的遍历      摘要: 图的常见遍历方式有两种:深度优先遍历和广度优先遍历,他们的作用是将图中的每个点都访问一遍,只不过是顺序不同。
如果把图中的每条边长都相等(比如都是1)的话,深度优先遍历的过程是:
1.任意选定一个点p0作为遍历的起点
2.从未访问节点中任选一个距离p0最近的点进行访问,并标记该点被访问过
3.重复第2步,直到该连通分支中的所有节点都被访问过  阅读全文
posted @ 2012-08-20 12:23 小鼠标 阅读(1581) | 评论 (0)  编辑
hdu3342--拓扑排序
posted @ 2012-08-18 17:39 小鼠标 阅读(592) | 评论 (0)  编辑
hdu1285--拓扑排序
posted @ 2012-08-18 17:17 小鼠标 阅读(209) | 评论 (0)  编辑
zoj1060,poj1094--拓扑排序      摘要: 下面我先说以下拓扑排序:
严蔚敏《数据结构》上的定义是:由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
直观的说偏序指集合中仅有部分成员之间可比较,而全序指集合中全体成员之间均可比较。
拓扑排序的具体做法是:
1.在有向图中选择一个没有前驱(入度为0)的顶点,输出
2.从图中删除该顶点和所有以它为尾的弧,并更新相关点的入度
3.重复1,2步,直到所有顶点都被输出,或者发现图中存在回路。  阅读全文
posted @ 2012-08-16 19:19 小鼠标 阅读(1771) | 评论 (0)  编辑
poj1135--Dijkstra
posted @ 2012-08-09 20:04 小鼠标 阅读(207) | 评论 (0)  编辑
poj3268--Dijkstra
posted @ 2012-08-09 16:18 小鼠标 阅读(215) | 评论 (0)  编辑
单源最短路径Dijkstra算法      摘要: dijkstra算法是解决单源最短路径问题的经典算法,具有O(N^2)的时间复杂度(N为节点个数),这种算法采用的是贪心策略,它与最小生成树的Prim算法极其相似,这两种算法仅仅是cost[]代表的含义不同……  阅读全文
posted @ 2012-08-08 16:27 小鼠标 阅读(1856) | 评论 (0)  编辑
poj2253--最短路Dijkstra
posted @ 2012-08-07 23:51 小鼠标 阅读(114) | 评论 (0)  编辑
poj2966--最小生成树Prim
posted @ 2012-08-07 11:23 小鼠标 阅读(111) | 评论 (0)  编辑
zoj1372--最小生成树
posted @ 2012-08-07 10:47 小鼠标 阅读(105) | 评论 (0)  编辑
最小生成树Prim算法
posted @ 2012-08-06 17:46 小鼠标 阅读(3111) | 评论 (0)  编辑

Full 图论 Archive

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜