图论:Prufer编码

时间:2022-10-26 19:03:04

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 - ) ! / ( (d1 - )! (d2 - )! ……(dn - )! ) 

这样就是答案了

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

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

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

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

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

s用来预处理阶乘

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

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

满足题目的需求,直接计数即可:

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

下面给完整的代码:

 #include<cmath>
#include<cstdio>
const int maxn=;
int n,tot,cnt;
int pri[maxn],d[maxn],num[maxn];
long long ans=;
long long s[];
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>'') {if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='') {x*=;x+=ch-'';ch=getchar();}
return x*f;
}
bool jud(int x)
{
for(int i=;i<=sqrt(x);i++)
if(x%i==) return ;
return ;
}
void getpri()
{
for(int i=;i<=;i++)
if(jud(i)) pri[++cnt]=i;
}
void solve(long long x,int f) //按照指数分解质因数
{
for(int i=;i<=cnt;i++)
{
if(x<=) return;
while(x%pri[i]==) {num[i]+=f;x/=pri[i];}
}
}
int main()
{
s[]=;
for(int i=;i<=;i++) s[i]=s[i-]*i;
getpri();
n=read();
if(n==)
{
int x=read();
if(x==) printf("");
else printf("");
return ;
}
for(int i=;i<=n;i++)
{
d[i]=read();
if(d[i]==) {printf("");return ;}
d[i]--;
tot+=d[i];
}
if(tot!=n-) {printf(""); return ;}
solve(s[n-],); //计算阶乘并将结果分解质因数
for(int i=;i<=n;i++) solve(s[d[i]],-); //同上
for(int i=;i<=cnt;i++)
while(num[i]--) ans*=pri[i]; //统计结果
printf("%lld",ans);
return ;
}

图论:Prufer编码的更多相关文章

  1. 图论:Prufer编码-Cayley定理

    BZOJ1430:运用Cayley定理解决树的形态统计问题 由Prufer编码可以引申出来一个定理:Cayley 内容是不同的n结点标号的树的数量为n^(n-2) 换一种说法就是一棵无根树,当知道结点 ...

  2. 树的prufer编码

    prufer是无根树的一种编码方式,一棵无根树和一个prufer编码唯一对应,也就是一棵树有唯一的prufer编码,而一个prufer编码对应一棵唯一的树. 第一部分:树编码成prufer序列. 树编 ...

  3. 【转】prufer编码

    既然有人提到了,就顺便学习一下吧,来源:http://greatkongxin.blog.163.com/blog/static/170097125201172483025666/ 一个含有n个点的完 ...

  4. &lbrack;BZOJ1430&rsqb; 小猴打架 &lpar;prufer编码&rpar;

    Description 一开始森林里面有N只互不相识的小猴子,它们经常打架,但打架的双方都必须不是好朋友.每次打完架后,打架的双方以及它们的好朋友就会互相认识,成为好朋友.经过N-1次打架之后,整个森 ...

  5. Codeforces 1109D&period; Sasha and Interesting Fact from Graph Theory 排列组合&comma;Prufer编码

    原文链接https://www.cnblogs.com/zhouzhendong/p/CF1109D.html 题意 所有边权都是 [1,m] 中的整数的所有 n 个点的树中,点 a 到点 b 的距离 ...

  6. prufer编码

    看51nod的一场比赛,发现不会大家都A的一道题,有关prufer的 我去年4月就埋下prufer这个坑,一直没解决 prufer编码是什么 对于一棵无根树的生成的序列,prufer序列可以和无根树一 ...

  7. &lbrack;bzoj1005&rsqb;&lbrack;HNOI2008&rsqb;明明的烦恼-Prufer编码&plus;高精度

    Brief Description 给出标号为1到N的点,以及某些点最终的度数,允许在 任意两点间连线,可产生多少棵度数满足要求的树? Algorithm Design 结论题. 首先可以参考这篇文章 ...

  8. BZOJ 1430 小猴打架(prufer编码)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1430 [题目大意] 一开始森林里面有N只互不相识的小猴子,它们经常打架, 但打架的双方 ...

  9. 【Foreign】树 &lbrack;prufer编码&rsqb;&lbrack;DP&rsqb;

    树 Time Limit: 10 Sec  Memory Limit: 256 MB Description Input Output Sample Input 3 2 2 1 Sample Outp ...

随机推荐

  1. Xcode磁盘空间大清理

    我的设备是Macbook Air 13' Mid 2011,128G SSD.最近开始有些存储压力了,用Clean My Mac清理一部分旧文件后,决定对Xcode动手. 移除对旧设备的支持 影响:可 ...

  2. RabbitMq基本使用

    1.新建一个vhost : rabbitmqctl add_vhost test 2.新建一个用户: rabbitmqctl add_user news news 3.对这个news用户增加test ...

  3. Debug Assertion Failed&excl; Expression&colon; &lowbar;pFirstBlock &equals;&equals; pHead

    点击Abort之后,查看调用栈,发现异常在函数return时被时产生,进一步看是vector的析构函数被调用时产生,以前没开发过C++项目,没什么经验,这个错误让我很困惑,第一,我电脑上并没有f盘:第 ...

  4. DB2测试存储过程的原子性

    存储过程在运行过程中需要对其做异常处理.原子性等测试 下面是一个原子性测试案例 ===================================== 代码区域 ================= ...

  5. 如何使用axis2 构建 Android 服务器后端--- 工具准备与环境配置

    最近一个项目要做个android端的实验室器材管理系统.小伙伴英勇地接下android端的锅,我就 负责给他写后端,最近看到axis2 这个webservice挺好用的,折腾了几天给大家分享下: 1. ...

  6. 基于LINUX的多功能聊天室

    原文:基于LINUX的多功能聊天室 基于LINUX的多功能聊天室 其实这个项目在我电脑已经躺了多时,最初写完项目规划后,我就认认真真地去实现了它,后来拿着这个项目区参加了面试,同样面试官也拿这个项目来 ...

  7. Kafka官方文档翻译——简介

    简介 Kafka擅长于做什么? 它被用于两大类应用: 在应用间构建实时的数据流通道 构建传输或处理数据流的实时流式应用 几个概念: Kafka以集群模式运行在1或多台服务器上 Kafka以topics ...

  8. 如何运行 rpcz python example

    试着运行 rpcz-python 的 example.过程记录如下.假设protobuf-py已经按照protobuf的安装说明安装了.发现 protobuf-2.5.0版的python包是pytho ...

  9. C&num; Tuple&lt&semi;T1&comma;T2&period;&period;&period;&period;T&gt&semi;元组的使用

    1) 先说组元:一个数据结构,由通过逗号分割的,用于传递给一个程序或者操作系统的一系列值的组合. NET Framework 直接支持一至七元素的元组 Tuple<T1> Tuple&lt ...

  10. 【Codeforces 710F】String Set Queries

    Codeforces 710 F 思路:KMP学的还是不过关啊... 按照字符串的长度分类,如果长度大于\(\sqrt{n}\)的就扔到什么地方等待查询,否则就扔进trie里面. 对于查询,我们先在t ...