Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Problem A

Posted by ACRush at 2009-11-01 11:03:56
In Reply To:武汉赛区比赛9:00-14:00，清华校内PK最终决战 Posted by:ACRush at 2009-11-01 08:59:48

说说A吧，很tricky的问题

给定一些Process的约束信息，除此之外，然后计算最少需要的时间，并且输出方案。

如果只要求计算第一问，这题是明显的简单题。

我也没有想到第二问比较高效的做法，说一个比较慢的方法吧：

对于一个网络G，可以在O(N)时间内算出需要的时间，用T(G)表示
(1)如果存在CUT G=G1+G2，使得T(G)=T(G1)+T(G2)，那么对G1和G2分别构造
(2)否则，一定是一个纠结在一起几条可以看作链结构的网络，我们可以计算出两个G3,G4，使得T(G)=max(T(G3),T(G4))，其中G3,G4之间没有边，然后分别构造然后用|连起来

时间复杂度至少需要O(N^2)

Followed by:

Re:Problem A (34) rujialiu 2009-11-01 11:07:59
- Re:Problem A (65) Siyao 2009-11-01 11:11:25

Post your reply here:

Home Page Go Back To top