图上的困惑

Question

给定一个无向图G=(V，E)，每个节点i与对象的'Ci‘数相关联。在每一步中，对于每个节点i，Ci对象在I的邻居之间被平均分配。经过K步，输出对象最多的前五个节点的对象数。

下面是一个步骤中发生的事情的一个例子：

A的对象被B和C平分。

B的对象被A和C平分。

C的对象被A和B平分。

一些约束：|V|<10^5，|E|<2*10^5，K<10^7，Ci<1000

我目前的想法是:用矩阵表示每个步骤中的转换。将该问题转化为矩阵幂的计算。但是这个解太慢了，考虑到x-V可以是10^5。

有什么更快的方法吗？

Answer 1

一个步骤的矩阵方程类似于M x = x'，其中x是当前节点内容的向量，x'是一步之后的内容。就是，x' = M x。后面一步的内容是x" = M x' = M(M x)。下面是一个M的例子，图的邻接矩阵显示在左边。标题为#nbr的列是节点a，b的邻居数。矩阵M是由邻接矩阵通过用等于同一列的数的分数替换每个1而形成的。

  a b c d e  #nbr          matrix M
a 0 0 1 1 0   2       0   0  1/3 1/4  0
b 0 0 0 1 0   1       0   0   0  1/4  0
c 1 0 0 1 1   3      1/2  0   0  1/4 1/2
d 1 1 1 0 1   4      1/2  1  1/3  0  1/2
e 0 0 1 1 0   2       0   0  1/3 1/4  0

要执行以初始内容x开头的K步，只需计算(M^K) x。使用一个指数法，它需要lg K矩阵乘法，lg表示对基2的对数。由于矩阵乘法通常具有O(n^3)复杂度，这种方法如果直接实现，则为O(lg K* n^3)，如果使用Coppersmith/Winograd算法，则为O(lg K* n^2.376)。通过lg K M将复杂度降到O(n^2.376)，即把对角化乘子降为(P^-1)AP，其中M^K = (P^-1)(A^K)P和A^K是O(n lg K)运算，给出了O(n^2.376)的整体运算。对角化通常花费O(n^3)，但代价是O(n^2.376) 利用Coppersmith/Winograd算法。