Just For Fun,HDU Navigater
HDU Navigater只用到一个算法,SPFA算法,直接把以前写过的 C代码移植 为Java就哦了,白天写,晚上就要交,所以时间紧张,代码移植的很C,一点没Java的风格,不过先用着吧。
Thanks God,It’s Friday
“ 它确实使人们想起 Ken Thompson 在早期 UNIX 的源代码中所写的一句著名的注释:
/*You are not expected to understand this */ ”
计算几何学(Computational Geometry)
如图 a)→b) 过程中,原本p2在栈S中,到 b) 时,根据p1p3,p1p2的叉积计算,得知 p1p3 在 p1p2 的顺时针方向行,所以 p2 不在CH(Q)中,所以 p2 出栈,p3入栈,整个算法都循环这个过程,后续完整图示:
矩阵乘法(Matrix Multiply)
两个矩阵 A,B:A 的列数等于 B 的行数,则A、B可以相乘。即,如果 A = (aij)是一个m * n的矩阵,B =(bjk)是一个 n * p 的矩阵,则它们的乘积 C = AB 是 m * p 矩阵 C = (cik)。
网络流(Network Flow)
将每条有向边想象成传输物质的管道。每个管道都有一个固定的容量,可以看作是物质能流经该管道的最大速度(譬如可以想象为水流和河槽)。顶点是管道间的连接点,除了源点(S,Source)和汇点(T,Target)以外,物质只流经这些顶点。而不聚集在顶点中。
最短路算法(Shortest Paths Algorithm)
SPFA算法是西南交通大学段凡丁于1994年发表的。它是Bellman-Ford的队列优化,时效性相对好,时间复杂度O(kE),也是单源最短路算法,同时可以处理负权边。从名字即可看出,此算法速度非同一般。
最小生成树(Minimum Spanning Trees)
假设要在 n 个城市之间建立通讯联络网,则连通 n 个城市只需要修建 n-1条线路,如何在最节省经费的前提下建立这个通讯网?答案就是:最小生成树。术语描述就是:在 e条带权的边中选取 n-1 条边(不构成回路),使“权值之和”为最小。
图搜索算法(Graph Search Algorithm)
(a)是图的邻接表表示,(b)是图的邻接矩阵表示。图22-1 >>> a)一个有5个顶点和7条边的无向图G。b)G的邻接表表示。c)G的邻接矩阵表示。下图u示邻接矩阵表示法,图22-2 >>> a)有6个顶点和8条边的有向图G。b)G的邻接表表示。c)G的邻接矩阵表示。
并查集(Disjoint Sets)
是在FIND-SET操作中,把查找路径上的每个结点都直接指向根结点。路径压缩并不改变结点的秩。关于路径压缩,看图理解,之间为FIND-SET操作前集合,之后为FIND-SET操作后集合。此时,查找路径上的每一个结点都直接指向根。














