主题:求助大家了..AOE网的题目怎么做
enmamade
[专家分:0] 发布于 2006-08-02 09:28:00
看了几遍书,还是不太明白,每个顶点事件的最早最晚发生时间和每个活动的最早最晚开始时间..题目的图画不出
a4=3
v2 v5 a8=1
a1=3 a3=2
a7=2
v1 v4 v6
a2=2
a5=4 a6=3
v3
v1→v2 v1→v3 v2→v4 v2→v5 v3→v4 v3→v6 v5→v6 v4→v6
麻烦各位朋友能指点一下,告诉我方法。
顺便问一句,考软件设计师,数据结构中各个算法是否都要记下来。。
不剩感激!
回复列表 (共8个回复)
沙发
gclu0212 [专家分:90] 发布于 2006-08-02 15:02:00
其实不难 求最早时间是从开始结点 往 终点做 而最晚时间是等最早时间求出后 从终点往开始结点做. 求最早时间,是取最大值 求最晚时间,是取最小值.
你这张图虽然有结点 有代价 有路径 但太乱的 看不清 最好截张图;
软件设计师的考试有考纲的 并不是全要
考纲:http://www.kaozi.com/KSdagang/02.htm
板凳
enmamade [专家分:0] 发布于 2006-08-02 16:25:00
[img]http://cache34.51.com/photo3/0d/17/nalong123/2095b49cadab5ae5a555ad276081e459.jpg[/img]
图传上来了,麻烦上边的朋友说一下详细的解法!
3 楼
rickone [专家分:15390] 发布于 2006-08-02 20:51:00
最早发生时间就看它的入度上的弧,前面的结点的最早发生时间+弧上的时间,取最大值;
最迟发生时间就看它的出度上的弧,后面的结点的最迟发生时间-弧上的时间,取最小值。
一开始,入度为0的结点上的最早发生时间是0,往后推,到最后一个结点,如果它的最早发生时间是t,那令它的最迟发生时间也是t,反过来再求其它结点的最迟发生时间,如果结点上的最早最迟发生时间相等,就是关链结点,连起来构成关链路径。
哈哈,希望我没错,好久没看这部分内容了。
考软件设计师,数据结构中各个算法是否都要记下来? ----- 是的。
4 楼
rickone [专家分:15390] 发布于 2006-08-02 20:58:00
上面的图,a3(v2 -> v4)没有指定
5 楼
rickone [专家分:15390] 发布于 2006-08-02 21:06:00
v1(0,)
v2(3,) v3(2,)
v4(max{3+2,2+4}=6,)
v5(6,)
v6(max{2+3,6+2,6+1}=8,)
v6(8,8)
v5(6,7) v4(6,6) v3(2,5)
v2(3,min{7-3,6-2}=4)
v3(2,min{6-4,8-3}=2)
v1(0,0)
最终:v1(0,0) v2(3,4) v3(2,2) v4(6,6) v5(6,7) v6(8,8),关链路径:v1-v3-v4-v6
6 楼
gclu0212 [专家分:90] 发布于 2006-08-03 00:45:00
楼上正解
7 楼
enmamade [专家分:0] 发布于 2006-08-03 09:40:00
好的`` 看明白了 谢谢楼上各位的帮忙
特别感谢rickone 嘿嘿..
大学都过了3年了,转眼才发现自己什么都没学到,只好恶补了
不知道哪位是学的计算机科学与技术,不知道就业前景怎么样呢
ps:我现在是主攻vc++
8 楼
gclu0212 [专家分:90] 发布于 2006-08-04 12:41:00
我也是计算机专业的 也是大三!
我来回复