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 |
一点思考历程找权能增加的环 (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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator