求 DAG 拓扑排序方案数

StayAlone · 2023-03-09 17:23:11 · 题解

例题

此题可以直接转化为对 x_i\to y_i 连边后，拓扑排序的方案数。此问题无多项式复杂度解，可以通过状压做到 \mathcal O(n\cdot2^n)。

设 f_s 表示选择点集为 s，满足要求的方案数。转移时通过类似拓扑的顺序转移。

若当前的点集为 s，考虑新增一个点 x。定义增加后的点集为 s'。若这个点的所有儿子都在点集 s 中，且这个点不在点集 s 中，则可以钦定 x 放在最前面，那么 f_{s'} 中就要累加一个 f_s。因此，找到所有满足条件的 x，就可以获得答案。换句话说，就是对于一个点集，累加当某个点在最前面时的方案数。

写了两种写法，一种顺推，一种记搜。都还挺好理解的。

写法一：

int n, m, son[MAXN]; ll f[MAXN];

int main() {
    read(n, m);
    rep1(i, 1, m) {
        int x, y; read(x, y);
        son[x] |= 1 << y - 1;
    } f[0] = 1;
    rep1(s, 0, (1 << n) - 1) rep1(x, 1, n) {
        if ((son[x] & s) == son[x] && !(s >> x - 1 & 1)) f[s | (1 << x - 1)] += f[s];
    } printf("%lld", f[(1 << n) - 1]);
    rout;
}

写法二：

int n, m, son[MAXN]; ll f[MAXN];

il ll dfs(int s) {
    if (~f[s]) return f[s];
    f[s] = 0;
    rep1(i, 1, n) {
        int s2 = s ^ (1 << i - 1);
        if (s >> (i - 1) & 1 && (son[i] & s2) == son[i]) f[s] += dfs(s2);
    } return f[s];
}

int main() {
    read(n, m);
    rep1(i, 1, m) {
        int x, y; read(x, y);
        son[x] |= 1 << y - 1;
    } f[0] = 1; fill(f + 1, f + (1 << n), -1);
    printf("%lld", dfs((1 << n) - 1));
    rout;
}