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

度限制生成树，一个从最小生成树修改的贪心

Posted by dynamic at 2004-01-10 11:38:59 on Problem 1639
In Reply To:谁能提示一下这题该怎么做？ Posted by:hujialie at 2004-01-08 23:29:47

Followed by:

有界度生成树不是np-hard的问题吗 (17) hawk 2004-01-10 12:40:36
- degree-bounded minimum spanning tree是NP hard的，不过这里只对一个点有degree的要求，比较不同 (21) dynamic 2004-01-10 15:09:19
具体该怎么贪呢？是求出最小生成树后贪心修改呢，还是在求树的过程中贪心？ (0) hujialie 2004-01-11 17:23:55
- 两种都可以，对应的是两种不同的算法 (0) dynamic 2004-01-11 18:52:35
  - 用枚举最后到park的路径里<=限制的度的边再用最小生成树连对吗？ (0) ACM29084 2004-10-23 09:37:14

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator