学步园

题目描述：

某人要对拳皇的人物做一个排序。输入一个N，接下来N行每行两个字符串A B，表示A比B厉害。要求一共有多少种不同的拓扑排序方法。若不能完成排序输出0。

分析：

可以用动态规划来解决。

对于n个节点进行拓扑排序，设当前有m个度为0的节点，记为Zi。所以当前可以选择这m个度为0的节点中的任意一个排在前面，剩下的节点有多少种排序方法与之前无关。

所以可以用节点集合表示状态。状态的转移也就是从当前集合去掉某个度为0的节点。

那么，状态S的计数总数 = ∑ 从S去掉Zi的计数总数。

当只剩下一个节点的时候，排序方法数为1。

/*
ZJU1346 Comparing Your Heroes
*/

#include 
#include 

#define N 20
#define M 100001
#define clr(a) memset(a,0,sizeof(a))

int n;
int hash[M];
int a[N][N];
int dp[M];
int error;

int ELFhash(char *key){ 
    unsigned long h=0; 
    while(*key){ 
        h=(h << 4) + *key++; 
        unsigned long g=h & 0Xf0000000L; 
        if (g) h^= g >> 24; 
        h &= ~g; 
    } 
    return h % M;
}

int ID(char s[]){
    int h = ELFhash(s);
    if(!hash[h]) hash[h]=++n;
    return hash[h];
}

int Encode(int e[]){
    int i,c=0;
    for(i=1;i<=n;i++){
        if(e[i]) c|=1<<(i-1);
    }
    return c;
}

int Count(int e[]){
    int c=Encode(e);
    if(dp[c]) return dp[c];
    if(error) return 0;
    
    int i,j,num=0;
    int z[N],pre,m=0;
    for(i=1;i<=n;i++){
        if(e[i]){
            num++;
            pre=0;
            for(j=1;j<=n;j++)
                if(e[j]&&a[j][i]) pre++;
            if(!pre) z[m++]=i;
        }
    }
    
    if(!m){ //不能完成拓扑排序 
        error=1;
        return 0;
    }
    if(num==1){ //只有一个节点 
        dp[c]=1;
        return dp[c];
    }
    
    int sum=0;
    for(i=0;i< m;i++){ 
        e[z[i]]=0;
        sum+=Count(e);
        e[z[i]]=1;
        if(error) return 0;
    }
    dp[c]=sum;
    
    return dp[c];
}

int main()
{
    int m;
    while(scanf("%d",&m)!=EOF){
        //init
        n=0;
        clr(hash);
        clr(a);
        clr(dp);
        
        //input
        int i,j,k;
        char s[N],t[N];
        
        for(k=0;k< m;k++){
            scanf("%s%s",s,t);
            i=ID(s);
            j=ID(t);
            a[i][j]=1;
        }
        
        //DP
        int e[N];
        for(i=1;i<=n;i++) e[i]=1;
        
        error=0;
        Count(e);
        
        //output
        k=Encode(e);
        if(error) printf("0/n");
        else printf("%d/n",dp[k]);
    }
    
    return 0;
}