Gym 102361F – Forest Program

题目链接:Gym 102361F

考虑每个简单环内至少取一条边,如果一个简单环有$x$条边,那么这个简单环的方案数为$\sum_{i=1}^{x} {x \choose i} = 2^x – 1$ ,对于非简单环上的边(即剩余的边)如果有$r$条,那么方案数为$\sum_{i=1}^{r} {r \choose i} = 2^r$,最后分步计数即可。

需要注意的是,这里没有保证整张图是联通的,只保证每个联通块是一个仙人掌,所以不能只DFS一个点。

 

说点什么

avatar
50
  Subscribe  
提醒