Dropbox OA Frenemy 求解

Kelsey_Xu 发表于 2016-2-2 08:09
谢谢大家！我已经用DFS加剪枝过啦~

楼主能否说一下剪枝的思路呢？非常感谢！

Kelsey_Xu 发表于 2016-2-2 08:09
谢谢大家！我已经用DFS加剪枝过啦~

楼主，请问你还记得dropbox的frenemy的剪枝条件是什么吗？实在不好意思打扰了。

dfs加剪枝应该是正确的做法，我生成了一个(800x800)的输入样例。根据测试的结果，dfs加剪枝是最快的，比dp快。

剪枝的方法，给你们一个信息好吧，用当前的 from 点和当前的relation的位置这个pair作为哈希key，如果该枝搜不到，就加到set里，后面遇见了直接返回false。

intijk 发表于 2016-3-11 15:23
dfs加剪枝应该是正确的做法，我生成了一个(800x800)的输入样例。根据测试的结果，dfs加剪枝是最快的，比dp ...

跪谢intijk! 在你的提示下，终于醒悟过来可以记录失败路径，避免重复搜索。秒过last 2 test case！