首页 > 代码库 > BZOJ 1005 明明的烦恼（Prufer数列）
BZOJ 1005 明明的烦恼（Prufer数列）
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1005
题意：给出一棵树的某些节点的度数d，有些未给。问满足这个条件的树有多少种？
思路：（1）Prufer 数列是无根树的一种数列。由一棵树可以构造出一个Prufer数列，Prufer数列可转化为原来的树。由树生成Prufer的一种简单方法是每次找出标 号最小的叶子节点将其父节点添加到Prufer数列并将该叶子节点删除。直到最后只剩下两个节点时结束。比如下面的这个树按照我们刚才的方法生成 Prufer数列为(3,5,1,3)。
（2）那么怎么由Prufer数列得到原来的那个树呢？设 {a1,a2,..an-2}为一棵有n个节点的树的Prufer序列，另建一个集合G含有元素{1..n}，找出集合G中最小的未在当前Prufer序 列中出现过的数，将该点与Prufer序列中首项连一条边，并将该点和Prufer序列首项删除，重复操作n-2次，将集合G中剩余的两个点之间连边即 可。仍以下面的树为 例，Prufer序列为{3,5,1,3}，开始时G={1,2,3,4,5,6}，未出现的编号最小的点是2，将2和3连边，并删去Prufer序列首 项和G中的2。接下来连的边为{4,5},{1,5},{1,3},此时集合G中仅剩3和6，在3和6之间连边，原树恢复。
（3）对于此题，设给定的度数的点有w个，令：
那么在最后的n-2个Prufer数列中这sum个是已经确定的，这sum个位置是给出的w个数的排列，排列数量为：
那么剩下的n-2-sum个位置上要放剩下的n-w个点，每个位置都有n-w种，所以最后的答案为：
import java.util.*;import java.text.*;import java.math.*;public class Main{ public static void PR(String s){ System.out.println(s); } public static void PR(int x) { System.out.println(x); } public static void PR(BigInteger x) { System.out.println(x); } public static void PR(double s) { java.text.DecimalFormat d=new java.text.DecimalFormat("#.000000"); System.out.println(d.format(s)); } static BigInteger p[]=new BigInteger[1005]; static BigInteger ans; static int d[]=new int[1005]; static int n; public static void main(String[] args){ Scanner S=new Scanner(System.in); n=S.nextInt(); int i; p[0]=BigInteger.ONE; for(i=1;i<=n;i++) p[i]=p[i-1].multiply(BigInteger.valueOf(i)); int sum=0,w=0,flag=1; for(i=1;i<=n;i++) { d[i]=S.nextInt(); if(d[i]!=-1) { sum+=d[i]-1; w++; } if(d[i]==0||d[i]>n-1) flag=0; } if(n==1) { if(d[1]==0||d[1]==-1) PR(1); else PR(0); } else if(n==2) { if((d[1]==-1||d[1]==1)&&(d[2]==-1||d[2]==1)) PR(1); else PR(0); } else if(flag==0) PR(0); else { ans=p[n-2].divide(p[n-2-sum]); for(i=1;i<=n;i++) if(d[i]!=-1) { ans=ans.divide(p[d[i]-1]); } for(i=1;i<=n-2-sum;i++) ans=ans.multiply(BigInteger.valueOf(n-w)); PR(ans); } }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。