闻说还能用在负权,和有环图...继续研究
const
int
MAXN
=
101
;
const
int
INF
=
1000000
;
int
g[MAXN][MAXN];
int
d[MAXN][MAXN];
int
floyd(
int
n)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
i, j, k;
for
(i
=
1
; i
<=
n; i
++
)
for
(j
=
1
; j
<=
n; j
++
)
d[i][j]
=
g[i][j];
for
(k
=
1
; k
<=
n; k
++
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for
(i
=
1
; i
<=
n; i
++
)
for
(j
=
1
; j
<=
n; j
++
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if
(d[i][k]
<
INF
&&
d[k][j]
<
INF
&&
d[i][k]
+
d[k][j]
<
d[i][j])
d[i][j]
=
d[i][k]
+
d[k][j];
}
}
return
0
;
}
posted @
2006-08-29 15:27 豪 阅读(1011) |
评论 (1) |
编辑 收藏
//------------------------------
给我一年时间, 把你们都搞
定, 呵呵, 做个好梦先!~
------------------------------//
图论
路径问题
最短路径
0/1 边权最短路径
BFS
非负边权最短路径
Dijkstra
u 可以用Dijkstra解决的问题的特征
负边权最短路径
Bellman-Ford
u Bellman-Ford的Yen-氏优化
u 差分约束系统
Floyd
u 广义路径问题
u 传递闭包
u 极小极大距离 / 极大极小距离
Euler Path / Tour
圈套圈算法
混合图的 Euler Path / Tour
Hamilton Path / Tour
特殊图的Hamilton Path / Tour 构造
生成树问题
最小生成树
第k小生成树
最优比率生成树
u 0/1分数规划
度限制生成树
连通性问题
u 强大的DFS算法
无向图连通性
割点
割边
二连通分支
有向图连通性
强连通分支
u 2-SAT
u 最小点基
有向无环图
拓扑排序
u 有向无环图与动态规划的关系
二分图匹配问题
u 一般图问题与二分图问题的转换思路
最大匹配
u 有向图的最小路径覆盖
u 0 / 1矩阵的最小覆盖
完备匹配
最优匹配
网络流问题
u 网络流模型的简单特征和与线性规划的关系
最大流最小割定理
最大流问题
有上下界的最大流问题
u 循环流
最小费用最大流 / 最大费用最大流
弦图的性质和判定
组合数学
u 解决组合数学问题时常用的思想
u 逼近
u 递推 / 动态规划
概率问题
Polya 定理
计算几何 / 解析几何
u 计算几何的核心:叉积 / 面积
u 解析几何的主力:复数
基本形
点
直线,线段
多边形
凸多边形 / 凸包
u 凸包算法的引进,卷包裹法
Graham 扫描法
u 水平序的引进,共线凸包的补丁
完美凸包算法
相关判定
两直线相交
两线段相交
点在任意多边形内的判定
点在凸多边形内的判定
经典问题
最小外接圆
近似O(n)的最小外接圆算法
点集直径
旋转卡壳,对踵点
多边形的三角剖分
数学 / 数论
最大公约数
Euclid 算法
扩展的Euclid算法
同余方程 / 二元一次不定方程
同余方程组
线性方程组
高斯消元法
u 解mod 2域上的线性方程组
u 整系数方程组的精确解法
矩阵
行列式的计算
u 利用矩阵乘法快速计算递推关系
分数
分数树
连分数逼近
数论计算
求N的约数个数
求phi(N)
求约数和
……
素数问题
概率判素算法
概率因子分解
数据结构:
组织结构
二叉堆
左偏树
胜者树
Treap
统计结构
树状数组
虚二叉树
线段树
u 矩形面积并
u 圆形面积并
关系结构
Hash 表
并查集
u 路径压缩思想的应用
STL 中的数据结构
vector
deque
set / map
动态规划 / 记忆化搜索
u 动态规划和记忆化搜索在思考方式上的区别
最长子序列系列问题
最长不下降子序列
最长公共子序列
一类NP问题的动态规划解法
树型动态规划
背包问题
动态规划的优化
u 四边形不等式
u 状态设计
u 规划方向(?)
常用思想
二分
最小表示法
posted @
2006-08-17 23:44 豪 阅读(1033) |
评论 (3) |
编辑 收藏
#include
<
iostream
>
using
namespace
std;
![](/Images/OutliningIndicators/None.gif)
const
int
MAXN
=
100
;
![](/Images/OutliningIndicators/None.gif)
class
UFset
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
public
:
int
parent[MAXN];
UFset();
int
Find(
int
);
void
Union(
int
,
int
);
}
;
![](/Images/OutliningIndicators/None.gif)
UFset::UFset()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
memset(parent,
-
1
,
sizeof
(parent));
}
int
UFset::Find(
int
x)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
if
(parent[x]
<
0
)
return
x;
else
{
parent[x]
=
Find(parent[x]);
return
parent[x];
}
//
压缩路径
}
void
UFset::Union(
int
x,
int
y)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
pX
=
Find(x);
int
pY
=
Find(y);
int
tmp;
if
(pX
!=
pY)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tmp
=
parent[pX]
+
parent[pY];
//
加权合并
if
(parent[pX]
>
parent[pY])
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
parent[pX]
=
pY;
parent[pY]
=
tmp;
}
else
{
parent[pY]
=
pX;
parent[pX]
=
tmp;
}
}
}
int
main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
return
0
;
}
有bug请指正:)
posted @
2006-08-16 20:22 豪 阅读(883) |
评论 (5) |
编辑 收藏
先是晚上睡不着, 一直在想那道DP题, 倒是让我AC掉了, 算是安慰。
然后下午pku e10, 看到别人都7题6题那样, 而我还是一题都做不出来, 那种情景, 真是... 最终只能做出《算法艺术》上讲过的那道加括号的DP, 再而确定了,书上的代码是错的, 那时候,在真的是不知道应该开心, 还是不开心好了。
到了晚上,我写了一个小时得6K的高精度, 结果换来了TLE, 真是欲哭无泪。
就是这样, 又做了一天的题目, 每天都是这样做了, 什么时候能看看书呢? 嗯, 就明天, 看Floyd和DP!
posted @
2006-08-11 02:08 豪 阅读(566) |
评论 (9) |
编辑 收藏
放假回去了一个星期,见一下apple, 爸爸妈妈,老同学,又跑回学校了。
没办法,现在连DP都写不出来的我, 再不花时间努力, 老师要求的400题是完成不了的。还好, 宿舍还有我的战友们, 所以也不会觉得寂寞, 至少还可以一起喝糖水啊^_^!
回来这两个星期, 都泡在了acm的题目上面, 本来说要学点英语的(还好期末英语没挂), 但是也无暇兼顾了, 可是我还是觉得进度有点慢, 或者我自己又开始浮躁了, 对于acm, 接触了半年了, 虽然参加了校赛和省赛, 拿了点小奖, 但是对比起那些有OI基础的牛牛和那些数学特强的牛牛门(比如一个月可以330题的ghost_wei), 我真的是菜到不能再菜了, 最郁闷的是, 到现在连DP都写不出来, 我到底什么时候才能达到一看到题目, 就能构造出DP状态的境界呢?
嗯, 要继续努力了,不能浮躁, 加油, 争取这个月把DP搞定!
posted @
2006-08-10 02:27 豪 阅读(357) |
评论 (1) |
编辑 收藏