图论：Prufer编码

BZOJ1211：使用prufer编码解决限定结点度数的树的计数问题

首先学习一下prufer编码是干什么用的

prufer编码可以与无根树形成一一对应的关系

一种无根树就对应了一种prufer编码

先介绍编码过程：

选择无根树中度数为1的最小编号节点（也就是编号最小的叶子节点），将其删除，把它的邻接点加入数组

不断执行上述操作直到树中仅剩两个节点

解码过程：

顺序扫描prufer编码数组，将扫到的第一个节点记为节点u,寻找不在prufer编码中的没有被标记的最小编号的节点v

连接u-v并把v标记，将u从prufer编码数组删除并扫描下一个节点

性质：

一个点的入度为d,那么它最多有可能在prufer编码中出现d-1次

prufer编码一共有n-2个数字，每个相同的数字出现d-1次

针对这道题，如果我们给出了每个点的度数要求，那么满足要求的树的个数就是可生成的不同的prufer编码的个数：

(n - 2) ! / ( (d1 - 1)! (d2 - 1)! ……(dn - 1)! )

这样就是答案了

下面介绍题目的实现方法（这个题比较简单，只是借助了prufer编码的性质进行计数，不涉及编码和解码的过程）

const int maxn=155;
int n,tot,cnt;
int pri[maxn],d[maxn],num[maxn];
long long ans=1;
long long s[25];

tot用来统计prufer编码中应有的节点数，看是否满足等于n-2

cnt用来计数素数的个数，便于分解质因数

pri里存的的是每一个质数，num里存的是质数出现的次数

s用来预处理阶乘

抛开这道题，我们重点应该学一学这个分解质因数的方法

void solve(long long x,int f)  //按照指数分解质因数 
{
    for(int i=1;i<=cnt;i++)
    {
        if(x<=1) return;
        while(x%pri[i]==0) {num[i]+=f;x/=pri[i];}
    }
}

满足题目的需求，直接计数即可：

    solve(s[n-2],1);  //计算阶乘并将结果分解质因数 
    for(int i=1;i<=n;i++) solve(s[d[i]],-1); //同上 
    for(int i=1;i<=cnt;i++)
        while(num[i]--) ans*=pri[i];  //统计结果 
    printf("%lld",ans);

下面给完整的代码：

 1 #include<cmath>
 2 #include<cstdio>
 3 const int maxn=155;
 4 int n,tot,cnt;
 5 int pri[maxn],d[maxn],num[maxn];
 6 long long ans=1;
 7 long long s[25];
 8 inline int read()
 9 {
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
12     while(ch>='0'&&ch<='9') {x*=10;x+=ch-'0';ch=getchar();}
13     return x*f;
14 }
15 bool jud(int x)
16 {
17     for(int i=2;i<=sqrt(x);i++)
18     if(x%i==0) return 0;
19     return 1;
20 }
21 void getpri()
22 {
23     for(int i=2;i<=150;i++)
24     if(jud(i)) pri[++cnt]=i;
25 }
26 void solve(long long x,int f)  //按照指数分解质因数 
27 {
28     for(int i=1;i<=cnt;i++)
29     {
30         if(x<=1) return;
31         while(x%pri[i]==0) {num[i]+=f;x/=pri[i];}
32     }
33 }
34 int main()
35 {
36     s[1]=1;
37     for(int i=2;i<=22;i++) s[i]=s[i-1]*i;
38     getpri();
39     n=read();
40     if(n==1)
41     {
42         int x=read();
43         if(x==0) printf("1");
44         else printf("0");
45         return 0;
46     }
47     for(int i=1;i<=n;i++)
48     {
49         d[i]=read();
50         if(d[i]==0) {printf("0");return 0;}
51         d[i]--;
52         tot+=d[i];
53     }
54     if(tot!=n-2) {printf("0"); return 0;}
55     solve(s[n-2],1);  //计算阶乘并将结果分解质因数 
56     for(int i=1;i<=n;i++) solve(s[d[i]],-1); //同上 
57     for(int i=1;i<=cnt;i++)
58         while(num[i]--) ans*=pri[i];  //统计结果 
59     printf("%lld",ans);
60     return 0;
61 }