题目: http://goo.gl/pS7Ru (放心 是真正的url)
这题是说 纽约市有N个junction (其实就是graph上的vertex)
整个graph有 M个edge, 是双向的..
每个node上有initial数量的zombie, 这些zombie每一个
单位时间都会随机选一个该node的neighbor向之移动
k是总共的时间
题目是要问: 最后 有最多zombie的五个node上的zombie数量
小弟我写出了解法, https://gist.github.com/3856634
但是光是在test 五个case就只有过了前三个case 其他都应该TLE
在自己的电脑上run 到最后可以run出正确答案, 显然我的algorithm还不够好
我的做法是brute force每一个时间都计算最后该时间expected
number of zombies. 但显然有更好的做法
在此请教不知道更快的做法是否是跟那只选五个最多的zombie node
有关? 但我还是不知道怎么做??

这题目真有趣! 但是不会做Orz

还要再实作稀疏矩阵 orz

是说我很好奇有最多zombie的五个node是 "最初" 有最多还是最后 "期望" 有最多的五个?如果是最后 "期望最多的五个" 要怎么做@@?

先做出 markov matrix M, 初始为 z(0) => z(t)=(M^t)*z(0)M是 n by n ，z(i) 是长度为 n 的向量

n,m到10^5, 2*10^5吗？这样(稀疏)矩阵乘法也OK?

不确定，要试试看 orz

suhorng大, 是期望最后的最多zombie的五个node...bruteforce很执白, 就是隔壁邻点的僵尸平均分散然后本点再加总...

麻烦的是 矩阵到10^10个元素 次方数又到10^7次方还要化为diagonal matrix去解 不知怎利用sparse性质

各位同学, 有没有解法是适合interview的?一般interview碰到这个问题如果还要实作矩阵 应该不太多见

次方那边其实不用在意, 因为又反复平方法, 最多只要做lg k量级的个数

只能过第一组测资 orz https://gist.github.com/3862459

我觉得症结点在于只需要前五名 所以应该可以简化很多东西如果直接用矩阵次方 由于矩阵太大 时间一定会爆炸的

我觉得最后的稳定状态是 #zombie/#node 也就是想成分子扩散 最后会变平均 只是在此之前还是要用暴力法跑每做完一个step就检查是否进入稳定状态发现这样也有问题 zombie不会留在原地 一些case会错...

Accept 了... 结果他的测资好像都会进入稳定态 orz也有可能是因为要四舍五入到整数，所以进入稳定态的时间会大幅减少 ??

cool! 解法是？

https://gist.github.com/3862459 下面的 zombie_ac.cpp

都不用用到k@@ 这…题目整人 s大写得好精练又好读!

我原本是在 k<1.6N 的时候会真的算矩阵值，不过还是 TLE所以就干脆把 k 拿掉乱算... 只能说他的测资不够强不然应该有很多反例，比如图并不是连通的，或是 k=1 之类的

还有个不是稳定态的反例是3个node 0-10-0 <=> 5-0-5我怀疑题目是不是数值range给错...

sparse matrix 会遇到一个问题，就是乘到最后矩阵是满的 @@

感谢stimim 还没验证但我也直觉相信不理K才是可行的因为我觉得最后只要稳态达到, 就不用管k了

可是他的 K 可以小到 1 ，不一定会到稳态，也不一定有稳态像 arton 就举了一个没有稳态的例子

不过zombie_ac.cpp里最后magic number 5是k=5的意思?所以如果k很小就照他的走, 如果k很大就看稳态?没有稳态就一直算到k就是了@_@

没有啊，那个 5 是他要的前五名

喔了解

要判断会不会进入稳态 只需观察eigenvalue就好了http://ppt.cc/bCZw不过要计算eigenvalue是非常花时间的问题...参考看看就好

我也有想过要去求eigenvalue ，不过好像没有比较简单 orz

eigendecom ->O(n^3) -> 爆炸

这是图论里面一个问题, 我晚点把証明写上来