图中的每个边都具有1的权重,图可以具有周期,如果节点具有自循环,则它可以是从0到无穷大的任何距离,具体取决于编号 . 我们采取自我循环的时间 .
我已经使用bfs解决了这个问题,但是对距离的约束是10 ^ 9的顺序,因此bfs很慢 .
我们将在形式(距离,源)的给定图形上询问多个查询,并且o / p是从源顶点开始精确地在给定距离处的节点列表 .
Constraints
1<=Nodes<=500
1<queries<=500
1<=distance<=10^9
我有一种感觉,会有很多重复的计算作为没有 . 节点很小,但我无法弄清楚如何在较小的问题中减少问题 .
有效的方法是什么?
编辑:我已经尝试过使用矩阵求幂,但对于给定的约束,它太慢了 . 问题的时间限制为1秒 .
2 回答
设
G = (V,E)
为您的图形,并按如下方式定义邻接矩阵A
:在此矩阵中,每个
k
:这意味着通过创建此矩阵然后计算指数,您可以轻松获得答案 .
对于快速指数计算,您可以使用exponent by squaring,这将产生
O(M(n)^log(k))
,其中M(n)
是nXn矩阵的cost for matrix multiplication .在同一图表上查找不同的查询时,这也可以节省一些计算 .
Appendix - claim proof:
基数:
A^1 = A
,确实在A
中定义,A[i][j]=1
当且仅当(V[i],V[j])
在E
中时假设:假设声明对所有人都是正确的
l<k
A^k = A^(k-1)*A
. 从归纳假设,A^(k-1)[i][j] > 0
iff从V[i]
到V[j]
的路径长度为k-1
.让我们检查两个顶点
v1,v2
,其索引为i
和j
.如果它们之间的路径长度为
k
,则为v1->...->u->v2
. 设u
的索引为m
.来自i.h.
A^(k-1)[i][m] > 0
因为有路径 . 另外A[m][j] = 1
,因为(u,v2) = (V[m],V[j])
是一个边缘 .自
A[m][j] > 0
和A^(k-1)[i][m] > 0
,然后A^(k-1)*A[i][j] > 0
如果没有这样的路径,则对于每个顶点
u
使得(u,v2)是边,从v
到u
没有长度k-1
的路径(其他v1->..->u->v2
是长度为k
的路径) .然后,使用归纳假设我们知道如果
A^(k-1)[i][m] > 0
然后A[m][j] = 0
,对于所有m
.如果我们在定义
A^k[i][j]
的总和中分配,我们得到A^k[i][j] = 0
QED
小注意:从技术上讲,
A^k[i][j]
是i
和j
之间的路径数k
. 这可以证明与上面类似,但更多地关注细节 .为了避免数字增长太快(因为您可能需要大整数来存储该值,因此会增加
M(n)
),并且由于您不关心0/1以外的值 - 您可以将矩阵视为布尔值 - 仅使用0/1值并修剪其他任何内容 .如果图表中有循环,那么您可以推断出
cycle * N + 1
中每个相邻节点之间存在链接,因为您可以根据需要进行迭代 .这让我想到了这个想法,我们可以利用这些循环来获得优势!
在检测周期时使用BFS,我们计算
offset + cycle*N
然后我们接近我们的目标(K)很容易搜索K.
例如
A - > B - > C - > D - > B K = 1000; S = A;
A - 0
B - 1
C - 2
D - 3
B - 1(4N)
在这里你可以检查
k - (1+4N) = 0
的地板()1000 - 1 - 4N = 0
>999 = 4N
>N=249
=>最好的B是249*4 + 1
=997
更简单的方法是计算:
round(k - offset, cycle)
从这里你可以只计算几个步骤 .
在此示例中(作为REGEX):
A(BCD){249}BCD