正难则反,首先考虑取补集。
注意到不合法相当于从点 1 出发能走到的点集与从点 2 出发的点集不交。
则考虑枚举这两个集合为 S,T。
设 fS 为在 S 的子图内让 1 能够走到每一个点的方案数,gT 类似。
则除了 S∪T 以外的点,其子图内的边可以随便定向。
但若是从 S∪T 连向外界的边则一定要指向 S∪T。
以及,S,T 之间不能有边相连。
容易发现枚举 S,T 的复杂度是 O(3n) 的。
如何求 fS?
再取补集,不合法的方案则是 1 能走到的点集是 S 的真子集。
考虑枚举这个真子集为 T,则 T 内就是一个子问题,即 fT;T 外的边随意定向;T 与外界相接的边必须指向 T。
此时复杂度依然为 O(3n)。
代码:
1 |
|