ZJU 1346 Comparing Your Heroes 状态压缩DP 拓扑排序的计数

做多校的时候遇见一个求拓扑排序数量的题，就顺便来写了一下。

题意：

　　你有个朋友是KOF的狂热粉丝，他有一个对其中英雄的强弱比较，让你根据这些比较关系来给这些英雄排名。问一共有多少种排名方式。

思路：

　　用dp[S]记录当前状态的数量。 S表示拓扑排序中当前阶段已经被排序的点的集合。然后就可以枚举当前排序的点，转移的条件是这个点的所有前驱都被排序，而且这个点没被排序。然后转移就好了，最终状态就是所有点都完成排序。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <time.h>

using namespace std;

const int INF = 1<<30;
const int MAXN = 16;

int dp[1<<MAXN];
int pre[MAXN]; //记录每个点的前驱集合
char name[MAXN][MAXN]; //记录每个人物的名字
char str[2][MAXN];
int n, m;

void input() {
    //读数据及其之间的关系。
    //并且把他们存起来，给每一个名字一个编号
    //处理出来每个点的前驱存在pre[]中
    int u, v;
    n = 0;
    memset(pre, 0, sizeof(pre));
    for (int i = 0; i < m; i++) {
        scanf("%s%s", str[0], str[1]);

        for (u = 0; u < n; u++) //找到这个字符串
            if (strcmp(name[u], str[0])==0)
                break;
        if (u==n) strcpy(name[n++], str[0]); //如果没找到，插入这个字符串

        for (v = 0; v < n; v++)
            if (strcmp(name[v], str[1])==0)
                break;
        if (v==n) strcpy(name[n++], str[1]);

        pre[v] |= (1<<u); //u是v的前驱，所以，把u加进v的前驱集合
    }
//for (int i = 0; i < n; i++) printf("%d ", pre[i]); puts(""); //输出前驱集合
}

void solve() {
    //动态规划
    //枚举每个状态(已经有拓扑序的集合)，然后枚举假如这个集合的点
    memset(dp, 0, sizeof(dp));
    dp[0] = 1; //初始状态

    for (int S = 0; S < (1<<n); S++) if (dp[S]!=0) { //剪枝
        for (int i = 0; i < n; i++) if (((S&pre[i])==pre[i]) && !(S&(1<<i))) { //i的前驱全部在此状态中，并且i不在
            dp[S|(1<<i)] += dp[S];
        }
    }

    printf("%d
", dp[(1<<n)-1]); //最终状态时所有点都被排序
}

int main() {
    #ifdef Phantom01
        freopen("ZJU1346.txt", "r", stdin);
    #endif //Phantom01

    while (scanf("%d", &m)!=EOF) {
        input();
        solve();
    }

    return 0;
}