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)代码