Uoj#37. 【清华集训2014】主旋律
题意:
- 给出一张$n$个点的有向图,询问有多少子图是强连通的。
- $n\le 15$。
题解:
- 原问题并不好做,考虑求有多少子图是不强联通的。
- 一个图是不强连通的,也就是缩点后大于等于$2$个点。
一种暴力
- 考虑用$f(S)$表示点集为$S$的$DAG$方案数。
- 枚举入度为$0$的点集,容斥转移:
- 。
- (此处$S,T$均为缩点后的点集)
- 其中$cross[T][S]$表示从点集$T$向点集$S$连接的单向边数。
- 这样光是$\rm dp$的复杂度就有$O(m\times 3^n)$,还不包括枚举强连通分量缩点后情况的部分。
更优秀的做法
- 上述暴力中系数只跟缩点后中$T$的大小(也就是原图中$T$被分为几个强连通分量)有关。
- 那么转移也可以写为:
- (此处$S,T$均为原图中的点集)
- 其中$g_k[T]$表示将$T$分为$k$个强连通分量的方案数,$h[S]$表示起终点都在$S$中的方案数。
- 其中$h[S]$很容易求出。
- 然后我们按$k$奇偶分类。
- 我们只需要计算$p[S]=\sum\limits_{k=1}^{\lfloor\frac{|S|+1}{2}\rfloor}g_{2k-1}[S]-\sum\limits_{k=1}^{\lfloor\frac{|S|}{2}\rfloor}g_{2k}[S]$和$cross[T][S-T]$即可。
- 设$dp[S]$为点集$S$组成了一个强连通分量的方案数。
- 可以得到转移:
- 这里$u\in T$是为了重复计数(不同顺序枚举子集)。
- 那么:
- 然后$cross[T][S-T]$可以在枚举$T$的时候一步步更改得到。
- 然后$\rm dp$复杂度就是$O(3^n)$的了。
代码:
1 |
|