当前位置: 代码迷 >> 综合 >> ACSL竞赛笔记:Graph Theory(2)
  详细解决方案

ACSL竞赛笔记:Graph Theory(2)

热度:73   发布时间:2023-12-07 03:20:41.0

使用矩阵可以解决求路径数量的问题。
求解过程如下:
在这里插入图片描述
此为原题图片
1建立一个表格,横纵标明A,B,C。
在这里插入图片描述

如果两个节点有边相连则在表格中填1,否则填0,注意单向边。因此,表格填完结果是
在这里插入图片描述
求该矩阵的平方,结果即为两步路径的数量
在这里插入图片描述
如果要求3步,4步,5步路径,只需及时矩阵M的3次方,4次方,5次方

  相关解决方案