BZOJ – 1016 – [JSOI2008]最小生成树计数

题目链接:BZOJ – 1016 – [JSOI2008]最小生成树计数

如果$x,y$都是图$G$的最小生成树,那么满足这两个性质:

  • 如果$x$中包含$k$条边权为$w$的边,那么$y$中一定也包含$k$条边权为$w$的边
  • $x,y$的连通性是相同的,都没有出现环

根据这两个性质,可以DFS枚举所有重复边的组合,然后判断这些组合是否满足连通性条件,最后用乘法原理计数。

 

说点什么

avatar
50
  Subscribe  
提醒