T28:徒競走

1）题目意思

给你一个有向无环图（DAG），有 N 个点、M 条边。拓扑排序是一个长度为 N 的排列，要求每条边 x -> y 中，x 必须排在 y 前面。

要你计算：这个 DAG 一共有多少种不同的拓扑排序方案，并输出这个数量（不取模，直接输出整数）。

N<=16，所以可以用状态压缩 DP。

---

2）思路解析（状态压缩 DP 计数拓扑序）

状态表示

用一个二进制 mask 表示已经放入拓扑序的点集合：

• mask 的第 i 位为 1 表示点 i 已经被放进序列
• dp[mask] 表示形成这个 mask 的放置方式数量

初始：

• dp[0] = 1（什么都没放，只有一种方式）

如何转移

在状态 mask 下，下一个能放的点 v 必须满足：

• v 还没放（mask 没有 v）
• v 的所有前驱点都已经放了

预处理每个点 v 的前驱集合 pre[v]（也是一个 bitmask）：

• 如果有边 x -> v，则把 x 加进 pre[v]

那么“所有前驱都已放”可以写成：

• (pre[v] & mask) == pre[v]

转移：

• dp[mask | (1<<v)] += dp[mask]

最终答案：

• dp[(1<<N)-1]

复杂度

状态数 2^N，每个状态枚举 N 个点，复杂度 O(N * 2^N)，N<=16 很轻松。

---

3）代码

#include <bits/stdc++.h>
using namespace std;

int main(){                                              // 主函数入口
    ios::sync_with_stdio(false);                         // 加速输入输出
    cin.tie(nullptr);                                    // 加速输入输出

    int N,M;                                             // N个点，M条边
    cin>>N>>M;                                           // 读入N和M

    static int pre[16];                                  // pre[v]：点v的所有前驱点集合（bitmask）
    for(int i=0;i<N;i++) pre[i]=0;                       // 初始化前驱集合为空

    for(int i=1;i<=M;i++){                               // 读入每条边
        int x,y;                                         // 边x->y
        cin>>x>>y;                                       // 读入x,y
        x--;                                             // 转0-based
        y--;                                             // 转0-based
        pre[y] |= (1<<x);                                // 把x加入y的前驱集合
    }

    int FULL=(1<<N)-1;                                   // FULL表示所有点都已放入的状态

    static unsigned long long dp[1<<16];                 // dp[mask]：方案数（用unsigned long long能装下样例3）
    for(int mask=0;mask<=FULL;mask++) dp[mask]=0;        // 初始化dp为0
    dp[0]=1;                                             // 初始状态dp[0]=1

    for(int mask=0;mask<=FULL;mask++){                   // 枚举所有状态
        unsigned long long cur=dp[mask];                 // 取当前方案数
        if(cur==0) continue;                             // 为0则跳过

        for(int v=0;v<N;v++){                            // 枚举下一个要放的点v
            if(mask&(1<<v)) continue;                    // v已在mask里则不能再放
            if((pre[v]&mask)!=pre[v]) continue;          // v的前驱没全放完则不能放
            int nmask=mask|(1<<v);                       // 新状态：把v加入mask
            dp[nmask]+=cur;                              // 累加方案数
        }
    }

    cout<<dp[FULL]<<endl;                                // 输出所有点都放完时的方案数
    return 0;                                            // 程序结束
}