首页 > 代码库 > ZJU 1346 Comparing Your Heroes 状态压缩DP 拓扑排序的计数
ZJU 1346 Comparing Your Heroes 状态压缩DP 拓扑排序的计数
做多校的时候遇见一个求拓扑排序数量的题,就顺便来写了一下。
题意:
你有个朋友是KOF的狂热粉丝,他有一个对其中英雄的强弱比较,让你根据这些比较关系来给这些英雄排名。问一共有多少种排名方式。
思路:
用dp[S]记录当前状态的数量。 S表示拓扑排序中当前阶段已经被排序的点的集合。然后就可以枚举当前排序的点,转移的条件是这个点的所有前驱都被排序,而且这个点没被排序。然后转移就好了,最终状态就是所有点都完成排序。
代码:
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 const int INF = 1<<30;19 const int MAXN = 16;20 21 int dp[1<<MAXN];22 int pre[MAXN]; //记录每个点的前驱集合23 char name[MAXN][MAXN]; //记录每个人物的名字24 char str[2][MAXN];25 int n, m;26 27 void input() {28 //读数据及其之间的关系。29 //并且把他们存起来,给每一个名字一个编号30 //处理出来每个点的前驱存在pre[]中31 int u, v;32 n = 0;33 memset(pre, 0, sizeof(pre));34 for (int i = 0; i < m; i++) {35 scanf("%s%s", str[0], str[1]);36 37 for (u = 0; u < n; u++) //找到这个字符串38 if (strcmp(name[u], str[0])==0)39 break;40 if (u==n) strcpy(name[n++], str[0]); //如果没找到,插入这个字符串41 42 for (v = 0; v < n; v++)43 if (strcmp(name[v], str[1])==0)44 break;45 if (v==n) strcpy(name[n++], str[1]);46 47 pre[v] |= (1<<u); //u是v的前驱,所以,把u加进v的前驱集合48 }49 //for (int i = 0; i < n; i++) printf("%d ", pre[i]); puts(""); //输出前驱集合50 }51 52 void solve() {53 //动态规划54 //枚举每个状态(已经有拓扑序的集合),然后枚举假如这个集合的点55 memset(dp, 0, sizeof(dp));56 dp[0] = 1; //初始状态57 58 for (int S = 0; S < (1<<n); S++) if (dp[S]!=0) { //剪枝59 for (int i = 0; i < n; i++) if (((S&pre[i])==pre[i]) && !(S&(1<<i))) { //i的前驱全部在此状态中,并且i不在60 dp[S|(1<<i)] += dp[S];61 }62 }63 64 printf("%d\n", dp[(1<<n)-1]); //最终状态时所有点都被排序65 }66 67 int main() {68 #ifdef Phantom0169 freopen("ZJU1346.txt", "r", stdin);70 #endif //Phantom0171 72 while (scanf("%d", &m)!=EOF) {73 input();74 solve();75 }76 77 return 0;78 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。