Re: 问个g的面试题

jffifa

2015/6/18镜像同步17 回复

【在 LXYXYNT 的大作中提到: 】 : 直接重新构图O(nlogn)求个MST不行么。。二叉堆Prim O(|E|lg|V|) 快速排序Kruskal O(|E|lg|E|) 他要要O(|V|lg|V|)

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

nuanyangyang机器人#1 · 2015/6/18

“新的mst一定不会用到在原图里却不在原mst里的边”是真的吗？或者能不能找出反例？

ykprocess机器人#2 · 2015/6/19

【在 nuanyangyang 的大作中提到: 】 : “新的mst一定不会用到在原图里却不在原mst里的边”是真的吗？或者能不能找出反例？聪明这个其实很容易证明，为了简单起见，假设边权都不相同，考虑kruskal算法（或者类似的拟阵的性质），我们是按照边权从小到大的处理那些边的。一条原图里的边(u,v)，之所以不出现在原图的MST里，是因为处理到了它的时候，u和v已经是连通了的。那么对于新图，我们对于所有的边再跑一次kruskal的算法，再处理到边(u,v)时，显然u和v还是已经连通了的，所以它还是不会出现在新图的MST中。 ps：严谨的来说，为什么u和v在新图中还是连通的，是因为在处理(u,v)的前面的边的时候，可以选择的边和点是原来的超集。假设u和v此时是不连通的，那么一定是至少有一条边权比（u，v）小的边，虽然出现在了原图的MST里，但是没有出现在新图的MST时，设这条边为(a，b），而这条边之所以在新图中没有加进去，是因为当考虑到它时，a和b已经是连通了的，在考虑连通性时，这就相当于是加了这条边...

nuanyangyang机器人#3 · 2015/6/19

如果这是真的，那么只要对“由原来的节点加上v组成的点集，和原来mst上的边和新的边组成的边集组成的图”求mst就行了。这个图一共只有N+1个节点，最多2*N+1条边，其中n是原来的节点数。这样任何E*log(N)的算法（N和E是点数和边数）就都是N*log(N)了。【在 ykprocess 的大作中提到: 】 : : 聪明 : 这个其实很容易证明，为了简单起见，假设边权都不相同，考虑kruskal算法（或者类似的拟阵的性质），我们是按照边权从小到大的处理那些边的。一条原图里的边(u,v)，之所以不出现在原图的MST里，是因为处理到了它的时候，u和v已经是连通了的。那么对于新图，我们对于所有的边再跑一次kruskal的算法，再处理到边(u,v)时，显然u和v还是已经连通了的，所以它还是不会出现在新图的MST中。 : ...................

qoshi机器人#4 · 2015/6/19

单纯膜拜暖神！发自「贵邮」

nuanyangyang机器人#5 · 2015/6/19

【在 qoshi 的大作中提到: 】 : 单纯膜拜暖神！ : 发自「贵邮」别……作为一个不太合格的ICPC选手表示惭愧

qoshi机器人#6 · 2015/6/19

【在 nuanyangyang 的大作中提到: 】 : : 别……作为一个不太合格的ICPC选手表示惭愧作为非ICPC选手无脸羞愧T_T

ykprocess机器人#7 · 2015/6/19

【在 nuanyangyang 的大作中提到: 】 : 如果这是真的，那么只要对“由原来的节点加上v组成的点集，和原来mst上的边和新的边组成的边集组成的图”求mst就行了。这个图一共只有N+1个节点，最多2*N+1条边，其中n是原来的节点数。这样任何E*log(N)的算法（N和E是点数和边数）就都是N*log(N)了。 : bingo

hh1562535601机器人#8 · 2015/6/19

单纯进楼膜拜。

Wizmann机器人#9 · 2015/6/22

弱弱问下。。。有O(V)的算法么。。。。来自「北邮人论坛手机版」