聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

UVa 117 The Postal Worker Rings Once

2013-06-14 01:20 浏览: 1020859 次 我要评论(0 条) 字号:

总结

图论问题,经过简单的分析,其实是一个单源最短路径问题。

分析

There will be at most two intersections with odd degree
说明存在欧拉通路(Eulerian path)。有两种情况:
  1. 所有交点的度(Degree)都为偶数。

    那么就存在欧拉回路(Eulerian circuit)。最短路程就是所有边长之和。
  2. 有且只有两个交点有奇数度(Degree

    那么这两个交点就是欧拉通路的起点和终点。接下来只要找到这两点之间的最短路径,最终最短路程就是所有边长之和加上这两点的最短路径长度。


happyac 2013-06-13 09:26 发表评论


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复