给定一个无向图 G=(V,E)，每个节点 i 都与“Ci”个对象相关联。在每一步，对于每个节点 i，Ci 对象在 i 的邻居之间平均分配。经过K步，输出对象最多的前5个节点的对象个数。
这是一步中发生的一个示例：
A 的对象被 B 和 C 平均分配。B
的对象被 A 和 C 平均分配。C
的对象被 A 和 B 平均分配。
一些约束：|V|<10^5, |E|<2*10^5, K<10^7, Ci<1000
我目前的想法是：用一个矩阵来表示每一步的转换。这个问题转化为矩阵幂的计算。但是考虑到|V|，这个解决方案太慢了。可以是 10^5。
有没有更快的方法来做到这一点？
单步的矩阵方程为M x = x'，其中x是当前节点内容的向量，x'是一步后的内容。即，x' = M x。之后步骤的内容是x" = M x' = M(M x)。下面是 M 的示例，其中图的邻接矩阵显示在左侧。标题列#nbr是节点 a, b ... e 的邻居数。矩阵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
要从初始内容开始执行 K 步x，只需计算(M^K) x. 使用需要矩阵乘法的求幂方法，表示以 2 为底的对数。由于矩阵乘法通常具有 O(n^3) 复杂度，因此如果直接实现，此方法为 O(lg K * n^3)，或 O(lg K * n^2.376) 如果使用 Coppersmith/Winograd 算法。复杂度可以降低到 O(n^2.376)——也就是说，我们可以通过将 M对角化为 (P^-1)AP 的形式来放弃乘数，其中, 和是 O(n lg K) 运算，给出O(n^2.376) 总体。对角化的成本通常为 O(n^3)，但使用 Coppersmith/Winograd 算法的成本为 O(n^2.376) 。lg Klglg KM^K = (P^-1)(A^K)PA^K