矩阵树定理 + 容斥原理.
- 如果把所有出现的边都加上,直接算生成树个数,可能会包括了有某些公司没有用边的情况.
- 于是减去 1 个公司不修路,其他公司随便修的方案数.再加上 2 个公司不修路的方案数…
- 二进制大力枚举每个公司的边考不考虑,用矩阵树定理算方案数,乘上容斥系数即可.
- 时间复杂度 O(2n⋅n3) .
二进制表示状态的题,下标从 0 开始会方便一些.
1 |
|
夢はここに 思い出は遠くに
矩阵树定理 + 容斥原理.
二进制表示状态的题,下标从 0 开始会方便一些.
1 | #include<bits/stdc++.h> |
Be the first person to leave a comment!