Daily Archive: 2015-08-23

分治算法简介——归并排序

  归并排序应用分治算法,具有O(nlogn)的时间复杂度,其工作流程可以概述为: 将长度为n的无序序列分割成n个子序列,每个序列包含1个元素; 重复将子序列相互合并称为有序序列,直到只剩下1个序列,即为排序后的序列。   一个例程如下所示:

mergeSort() 中,分配了一个临时…
Read more

SPFA算法简介

  SPFA(Shortest Path Faster Algorithm)算法是Bellman-Ford的一个增强版,SPFA算法在随机稀疏图上表现良好,尤其适用于带负权边的情况,但在最差情况下效率和Bellman-Ford一样糟糕。如果没有负权边,选择Dijkstra算法更佳。   SPFA算法的基本思想和Bellman-Ford一样,对于有V个顶点和E条边的图,Bellman-Ford需要V…
Read more

Bellman-Ford算法简介

  Bellman-Ford算法用于计算有向图中的单源最短路径。对于有V个顶点和E条边的图,Bellman-Ford的时间复杂度为O(V·E),效率低于Dijkstra算法。Bellman-Ford可以用于有负权边的情况,且能判断负权环,十分灵活。   Wiki上给出的Bellman-Ford算法的伪代码如下所示:

  算法的输入为…
Read more

POJ 3414. Pots

1. 题目 http://poj.org/problem?id=3414 Pots Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 12107 Accepted: 5110 Special Judge Description You are given two pots, having the volume of A and B…
Read more

URAL 1263. Elections

1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1643 1263. Elections Time limit: 1.0 second Memory limit: 64 MB The next in turn elections are to come soon. All the fences are postered with lea…
Read more