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
URAL 1416. Confidential
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1416 1416. Confidential Time limit: 2.0 second Memory limit: 64 MB Zaphod Beeblebrox — President of the Imperial Galactic Government. And by chan…
Read more
URAL 1434. Buses in Vasyuki
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1434 1434. Buses in Vasyuki Time limit: 3.0 second Memory limit: 64 MB The Vasyuki University is holding an ACM contest. In order to help the par…
Read more
URAL 1980. Road to Investor
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1980 1980. Road to Investor Time limit: 1.0 second Memory limit: 64 MB ‘How could I forget it? In T hours we must show the alpha-version of our g…
Read more
URAL 1753. Bookshelf
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1753 1753. Bookshelf Time limit: 0.5 second Memory limit: 64 MB A bookshelf has length L and borders of height h. A book of height H is standing …
Read more
POJ 3273. Monthly Expense
1. 题目 http://poj.org/problem?id=3273 Monthly Expense Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 18048 Accepted: 7226 Description Farmer John is an astounding accounting wizard and has …
Read more
POJ 2456. Aggressive cows
1. 题目 http://poj.org/problem?id=2456 Aggressive cows Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8456 Accepted: 4224 Description Farmer John has built a new long barn, with N (2 <= N…
Read more
POJ 1064. Cable master
1. 题目 http://poj.org/problem?id=1064 Cable master Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 30585 Accepted: 6482 Description Inhabitants of the Wonderland have decided to hold a regio…
Read more
POJ 3259. Wormholes
1. 题目 http://poj.org/problem?id=3259 Wormholes Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 36967 Accepted: 13562 Description While exploring his many farms, Farmer John has discovered a…
Read more