「JSOI2008」最小生成树-krukal+矩阵树定理

发布于 12 天前  34 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「JSOI2008」最小生成树-krukal+矩阵树定理

Description

给定一张图,求他的最小生成树个数。

\(n \leqslant 100, m \leqslant 1000\)

Solution

最小生成树具有这样两种性质:

  1. 最小生成树中,每种权值的边的条数固定。
  2. 不同的最小生成树中,某一种权值的边在加完后,图的联通情况相同。

所以把添加某种权值的边的过程看做生成一棵生成树的过程(每种边的权值一样),可以直接用矩阵树定理求解。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「JSOI2008」最小生成树-krukal+矩阵树定理


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!