首页 > 代码库 > HDU 4917 Permutation 拓扑排序的计数
HDU 4917 Permutation 拓扑排序的计数
题意：
一个有n个数的排列，给你一些位置上数字的大小关系。求合法的排列有多少种。
思路：
数字的大小关系可以看做是一条有向边，这样以每个位置当点，就可以把整个排列当做一张有向图。而且题目保证有解，所以只一张有向无环图。这样子，我们就可以把排列计数的问题转化为一个图的拓扑排序计数问题。
拓扑排序的做法可以参见ZJU1346 。
因为题目中点的数量比较多，所以无法直接用状压DP。 但是题目中的边数较少，所以不是联通的，而一个连通块的点不超过21个，而且不同连通块之间可以看做相互独立的。所以我们可以对于每个连通块分别求解，然后利用排列组合的知识，把他们组合起来。这样就可以得到最终解了。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <map> 12 #include <set> 13 #include <functional> 14 #include <time.h> 15 16 using namespace std; 17 18 typedef __int64 ll; 19 20 const int INF = 1<<30; 21 const int MAXM = 21; 22 const int MAXN = 50; 23 const ll MOD = (ll) 1e9+7; 24 25 ll dp[1<<MAXM]; // 26 ll combine[MAXN][MAXN]; //组合数 27 int Matrix[MAXN][MAXN]; //邻接矩阵，1表示正向边，-1表示反向边 28 int tmp[MAXM], pre[MAXM], num; //求每个连通块的拓扑序用 29 bool vis[MAXN]; //求连通块用 30 int n, m, tot; 31 ll ans; 32 33 void dfs(int u) { 34 int u2 = num; //当前点的标号 35 tmp[num++] = u; //把这个点加入集合 36 vis[u] = true; 37 38 int v; 39 for (int i = 1; i <= n; i++) if (Matrix[u][i]) { //如果有边 40 if (!vis[i]) dfs(i); //如果没找过先找后继 41 if (1==Matrix[u][i]) { 42 for (v = 0; v < num; v++) if (tmp[v]==i) { 43 pre[v] |= (1<<u2); //把这个点加入后继的前驱集合 44 } 45 } 46 } 47 } 48 49 ll calc() { //计算某个连通块的拓扑数量 50 memset(dp, 0, sizeof(dp)); 51 dp[0] = 1; 52 53 for (int S = 0; S < (1<<num); S++) if (dp[S]>0) 54 for (int i = 0; i < num; i++) if (((S&pre[i])==pre[i]) && !(S&(1<<i))) { 55 dp[S|(1<<i)] = (dp[S|(1<<i)]+dp[S])%MOD; 56 } 57 58 return dp[(1<<num)-1]; 59 } 60 61 void solve() { 62 memset(vis, false, sizeof(vis)); 63 ans = 1; 64 tot = n; 65 for (int i = 1; i <= n; i++) if (!vis[i]) { //搜连通块 66 memset(pre, 0, sizeof(pre)); num = 0; 67 dfs(i); 68 if (num<2) //只有一个或者两个点的情况，拓扑序时确定的 69 ans = (((num*combine[tot][num])%MOD)*ans)%MOD; 70 else 71 ans = (((calc()*combine[tot][num])%MOD)*ans)%MOD; 72 73 tot -= num; 74 } 75 76 printf("%I64d\n", ans); 77 } 78 79 int main() { 80 #ifdef Phantom01 81 freopen("HDU4917.in", "r", stdin); 82 // freopen("HDU4917.out", "w", stdout); 83 #endif //Phantom01 84 85 for (int i = 0; i < MAXN; i++) { //预处理组合数(杨辉三角) 86 combine[i][0] = 1; 87 for (int j = 1; j <= i; j++) 88 combine[i][j] = (combine[i-1][j-1] + combine[i-1][j])%MOD; 89 } 90 91 while (scanf("%d%d", &n, &m)!=EOF) { 92 memset(Matrix, 0, sizeof(Matrix)); 93 int u, v; 94 for (int i = 0; i < m; i++) { 95 scanf("%d%d", &u, &v); 96 Matrix[u][v] = 1; 97 Matrix[v][u] = -1; 98 } 99 solve();100 }101 102 return 0;103 }
写的时候，莫名其妙的wa了一发，要数据来对拍才发现是中间结果溢出了……所以，小心的调整运算顺序和适当的加括号很有必要。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。