首页 > 其他 > 详细

生成树计数及应用 Matrix-Tree

时间:2018-04-29 01:05:30      阅读:233      评论:0      收藏:0      [点我收藏+]

例:给定一个图,图上每条边是红色或蓝色,求恰有 k 条红边的生成树个数. n50.

Matrix-Tree定理,对于限制条件可以利用多项式,把红边边权设为 X,蓝边为1.

最后求行列式得到的多项式中 Xk的系数就是答案.同样这也是利用了边权乘积的那个推广.

至于多项式情况下不方便高斯消元的问题.通过代入具体的数插值求多项式就可以解决.

BZOJ 5297

SPOJ 104

https://www.cnblogs.com/zj75211/p/8039443.html

生成树计数及应用 Matrix-Tree

原文:https://www.cnblogs.com/Aragaki/p/8970015.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!