Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

矩阵树定理

用于求图的生成树的数量。

定义一棵生成树的权值为所有边权乘积,求所有生成树权值之和。

无向图

对于边 $(a, b, c)$ ,A[a][a] += c, A[b][b] += c, A[a][b] -= c, A[b][a] -= c

有向图

外向树

对于边 $(a, b, c)$ ,A[b][b] += c, A[a][b] -= c

内向树

对于边 $(a, b, c)$ ,A[a][a] += c, A[a][b] -= c

最后删去根节点(无向图中任意节点)的行、列,求行列式的值即可。