ACM

URAL 1225. Flags

1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1225 1225. Flags Time limit: 1.0 second Memory limit: 64 MB On the Day of the Flag of Russia a shop-owner decided to decorate the show-window of …
Read more

URAL 1119. Metro

1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1119 1119. Metro Time limit: 0.5 second Memory limit: 64 MB Many of SKB Kontur programmers like to get to work by Metro because the main office i…
Read more

Floyd–Warshall算法简介

  Floyd–Warshall算法用于寻找有向图中任意两点间的最短路径,即多源最短路径。该算法可用于带负权边的图,但不能用于带负权环的图。该算法需要比较每一组节点间所有的路径,时间复杂度为Θ(|V|^3)。   设有一个图G,有N个节点,编号为1,2,…,N。函数shortestPath(i, j, k) 返回当仅使用点集{1,2,…,k}为中间节点时,从节点i到达节点j…
Read more

Tarjan算法简介

  Tarjan算法由Robert Tarjan提出,可看作是Kosaraju算法的一个升级版,可用于获取有向图的强联通分量。该算法从任意起点开始进行DFS,每个节点只访问一次,其搜索树即为图的生成森林,图的强联通分量可以从森林的特定子树中恢复出来。   在使用栈进行DFS时,首先将任意节点入栈,然后递归地搜索与该节点相连的其他节点。某一节点u递归搜索结束时: 如果节点u和栈上节点u之前的其他节点…
Read more