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 阅读(579)
评论(5) 编辑 收藏 引用 所属分类:
其他