http://acm.pku.edu.cn/JudgeOnline/problem?id=1767Which is Next 二叉樹,好煩的題,要考慮好多情況。
http://acm.pku.edu.cn/JudgeOnline/problem?id=3333Co-workers from Hell搜索過的。
一開始沒有想到用搜索做,因為狀態有2^100之多,一直以為有多項式算法。
后來問幾個人都是搜的,才敢去做,結果0ms就過了。
兩個剪枝:
1、跳向前的邊,如果長度不如一步一步向前走那么長,那肯定不走。
2、往后跳的邊,肯定走。
關于這個題,之前我還想把它
轉換成最長路問題(每條邊只走允許一次),后來還是發現不能轉換。況且,就算轉換成了每條邊只允許走一次的最長路問題,我也不知道有什么好的算法,bellman-ford可以求最長路,但前提是無正環。
posted on 2007-08-17 11:47
LSM 閱讀(595)
評論(5) 編輯 收藏 引用 所屬分類:
其他