以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  两个算法题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=76130)

--  作者：kof02guy
--  发布时间：7/23/2009 11:19:00 PM

--  两个算法题
2 Given a directed weighted acyclic graph G = (V, E, W) and a vertex s, design an O(n+m) algorithm to find a longest path that starts from s, where n = |V|, m=|E|.  (Hint: Do topological sorting from s. (Only call DFS once.) Let v1 (= s), v2, v3, ...., vk, be the sorted sequence, k £ n. Define d(vi) to be the longest distance from s to vi. Initially, d(vi) = - ¥. Set d(v1) = 0.  If d(v1), d(v2), …, d(vi) have been computed, how to compute d(vi+1) ?)

3 There are n terminals on each side of a circuit board indexed with 1, 2, …, n from left to right, as shown in the following figure. We need to connect terminal i (1 ≤ i ≤ n) on the top side with a unique terminal π(i) on the bottom side. In other words, we need n lines (i, π(i)) (1 ≤ i ≤ n) to connect n pairs of terminals. The following figure shows an example.


Two lines (i, π(i)) and (j, π(j)) ( i &sup1; j) will cross each other if i < j but π(i) > π(j), or vice versa. Two lines are called compatible if they do not cross each other. We wish to find the largest set of mutually compatible lines so that they can be layout on the same layer of circuit without crossing each other.

Please model this problem as a graph problem first and then design an O(n2) algorithm to solve it.

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 17.578ms