[公开课] [Princeton] Algorithms, Part II (week 1)

wsmjmiisme 发表于 2014-4-20 17:30
我最后一个timing 没过，想了半天也没有优化的办法了，请问大神们有没有针对outcast有什么优化？

我的 ...

谢谢在ls分享你的思路！

这个问题的话，我觉得不是outcast的问题，还是SAP。
把SAP的时间缩短一点应该就能过。我记得我当时也是这里没有过，后来微微改了sap就过了，但是离我做这个作业也过去一周了，具体的细节有点忘记了

dengfy 发表于 2014-3-25 17:32
请教一下，如何排除 出现 2个以上root 的情况？？

forum里面有人说了，读synsets的时候把nouns都放一个bag里面，后面碰到v->w的pair就把v从bag里面删除，最后bag里面剩下来的就是root，超过1个就不是rooted DAG

rsun 发表于 2014-4-20 20:09
谢谢在ls分享你的思路！

这个问题的话，我觉得不是outcast的问题，还是SAP。

谢谢你的提醒，我再查查

wsmjmiisme 发表于 2014-4-20 17:30
我最后一个timing 没过，想了半天也没有优化的办法了，请问大神们有没有针对outcast有什么优化？

我的 ...

可以cache算过的dis[i,j]的value
另外 dis[i,j] = dis[j,i]

grassgigi 发表于 2014-4-22 09:45
可以cache算过的dis的value
另外 dis = dis[j,i]

哦！ 我试试！ 多谢！

my late homework......

交作业
。。。。。。。。

Done....

重新开课了！大家快来上啊！