| ||||||||||
| 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 | |||||||||
这个算法错的吧In Reply To:一个O(m)的算法 Posted by:xiaoMM at 2008-09-29 21:31:25 当前搜到的点可能与未搜到的white点相连 我想了一个mlog(n) 吧black节点做成堆,每个元素的权值是该点与white点集合的边树(度) ,每次取度数最小的,如果这个值小于white集合中点的个数,则讲将该点加入white集合中 并更新堆中顶点的个数,否则停止。更新次数为m次,每次log(n),所以最多mlog(n)的运算量 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator