Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一点思考历程

Posted by cmonkey at 2012-01-22 17:13:10 on Problem 2240 and last updated at 2012-01-22 17:17:59
找权能增加的环
(DFS搜有向图,由于是环,如果第一次搜到某点,确认其没满足条件的环,
则以后不管什么点到达该点,都不可能有满足条件的环,所以可不再考虑该点。
上述剪枝,需要判某被搜到的点,是在以前搜过的,还是当前这个环中的。
实现时,开始是加个标记表示点在第几次搜索时找到,后发现同一轮搜索可能出现出现多个环
而每个点又可能在多个环中...不能说换一个点就换一个环标号,那以前环中的标号不是还要改...
后来重新想,每次回溯时去掉该点就好了嘛,所以直接标记成-1,表示去掉。)
-------------
提交后WA了,推翻上述结论,搜过的未成功的点,在后面的搜索中是可能成功的。
例如:
A 1.0 B
B 1.0 C
B 5.0 D
C 0.1 D
D 1.0 A
dfs时,如果先搜ABCA是不成功的,如果这时标记搜过的D为舍弃,则ABDA就搜不到了。
所以这个剪枝是错的。不加的话,是TLE。时间复杂度不是很清楚,但应该不是O(N^3),
如果边不重的搜,是O(E),但边可能被重复搜到,当路径中加入新边时,其他边会被重复搜到,
同时每条边可能被多次当新边被加入到路径中。
哦,或者说要把所有路径搜一遍
对完全图,最坏情况,路径至少有n!条...

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


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