9
20
2012
0

USACO 2.4

 

Section 2.4 DONE 2012.09.12 TEXT Shortest Paths
DONE 2012.09.12 PROB The Tamworth Two [ANALYSIS]
DONE 2012.09.17 PROB Overfencing [ANALYSIS]
DONE 2012.09.18 PROB Cow Tours [ANALYSIS]
DONE 2012.09.19 PROB Bessie Come Home [ANALYSIS]
DONE 2012.09.20 PROB Fractions to Decimals [ANALYSIS]

 

2.4关需要应用基础的最短路径算法,此外还有一些模拟题,难度不大。

The Tamworth Two

状态空间很有限,可以直接模拟,直到John和牛相遇或者出现重复的状态。

Overfencing

特殊的最短路径问题,图中的边权全部为1,所以可以使用广度优先搜索,不用考虑松弛的问题。

Cow Tours

应用floyd-warshall算法,然后枚举加入的边。

Bessie Come Home

单源最短路径问题,使用Dijkstra算法解决。需要注意的是处理重边。

Fractions to Decimals

简单的模拟笔算除法,对于无限循环小数,在笔算过程中第二次出现同样的余数时则可判定循环节出现。

Category: USACO | Tags: usaco | Read Count: 617

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com