puppet_pyt的博客

最近点问题的分治思路：假定一个垂线L将所有点分成2份，递归求出左边和右边的最短距离dl,dr，当前最短距离便是d = min(dl,dr) 需要处理的便是在中间部分是否存在过穿过L的两点之间距离小于d 题目：http://acm.hdu.edu.cn/showproblem.php?pid=1007 /**分治 最近点问题***/ #include #include #include

拓扑排序的大致思路就是对一个有向无圈图顶点进行排序，找到任意一个入度（至于入度，我的话来说就是有多少个点指向自己）为0的顶点，显示该顶点，然后删除该点及其边，即该点所指向的其他顶点的入度都减1，然后同样方向对剩余部分处理。 拓扑排序的用途，使得如果存在一条从vi到vj的路径，那么排序中vj在vi的后面；暂时还没用到，以后可能会用；参考用书《数据结构与算法分析》，不得不说c++的容器的确方便了许多

差不多算是第一个了解的算法，主要是做pat甲级时要用，依照的是《数据结构与算法分析》这本书； /*dijkstra算法求最短路径 邻接表表示图**/ #include //#include #define NotAVertex (-1) #define INF (1<<30) #define MAX 500 using namespace std; static int numv