【BZOJ1016】【JSOI2008】最小生成树计数

这题做法好玄妙啊。。

直接上结论:对于每一种权值的所有边,其在最小生成树中的作用是固定的

也就是先求一遍最小生成树,然后对于每一种权值的边,记录他们对于最小生成树的贡献。那么对于从小到大枚举所有权值的边,枚举这一种权值中所有边选/不选,判断贡献是否与一开始的最小生成树中的相同。然后乘起来就可以了。

听说还可以用基尔霍夫矩阵。。去学了一下这个东西好像还挺好懂。。

好玄妙啊。。

说点什么

  Subscribe  
提醒