[原创]ZOJ 3604 Tunnel Network [Prüfer编码与Cayley公式] 【树】

Tabris

CSDN杂类

发布于：2017年2月7日

次浏览

[原创]ZOJ 3604 Tunnel Network [Pr üfer 编码与 Cayley 公式] 【树】

2017-02-07 18:40:56 Tabris_ 阅读数：297

博客爬取于 2020-06-14 22:41:49
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54914010

!!!! 摘自

题目链接 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3604

---------------------------------------------------------------------------------------------------.
Tunnel Network

Time Limit: 2 Seconds Memory Limit: 65536 KB

Country Far-Far-Away is a big country with N cities. But it is now under a civil war. The rebel uses the ancient tunnel network which connects all N cities with N-1 inter-city tunnels for transportation. The government army want to destroy these tunnels one by one. After several months fighting, some tunnels have been destoryed. According to the intel, the tunnel network have excatly S connected components now. And what government army further knows is that city 1, 2, ... , S belong to each of the S connected components. Since the government have little knowledge about the remaining tunnels, they ask you to calculate the number of possible networks of remaining tunnels.

Input
There are multiple test cases. The first line of input contains an integer T (T ≤ 500) indicating the number of test cases. Then T test cases follow.

Each case contains one line containing two integer N (2 ≤ N ≤ 2000) and S (2 ≤ S ≤ N), as described above.

Output
The number of possible networks now. Since the number might be very large, you should output the answer after modulo 1000000007.

Sample Input
4
3 2
4 2
5 3
100 50

Sample Output
2
8
15
113366355

---------------------------------------------------------------------------------------------------.
题目大意：n 个城市（标记 1...n）由 n-1 条通道组成，其中的一些通道已经被破坏了，已知现有 s 个联通，城市 1...s 分别属于第 1...s 个联通，想要知道剩下通道网络可能的数目。

解题思路：
Pr üfer 编码与 Cayley 公式 from matrix67
明确了上述公式就简单了。

首先要知道 Prufer sequence.这是一个双射，能把一棵节点为 n 个的标号树树唯一映射成一个 n-2 的序列，反之一个 n-2 的序列能唯一映射成一个树。这题求树的形态数目可以转化为求序列的数目。
因为是要得到 s 棵树，所以可以增加一个节点 0，让 1...s 的父节点都为 0。Prufer seq 是每次找最小的标号，这里每次找最大的标号，本质一样的。
然后就是构造将 s+1...n 添加到 1...s 之后的事情。构造如下的图的树：

但是要如何保证构造出来的序列能映射成根为 0，第一层为 1...s ， 剩下的为 s+1...n 呢？
1、序列最后 s-1 个数字为 0,
2、倒数第 s 个数字在 1...s 之间
第一个理由是很容易想的。因为我们构造的 Prufer seq 每次找最大标号的叶子（度为 1）节点，所以在第一层的叶子被消去之前第一层以下的所有节点一定会被消去。而 1...s 的父节点都是 0
第二个的话要一点证明：
假如第一层存在一个最大值 x（x>s），那么第一层一下存在一个 y（1<=y<=s）。
因为最后 s-1 个数字都为 0，所以 x 是在 y 之后被消去的。
假如 y 的父节点是 x：
因为 y 比第一层之下所有节点标号都大，所以必定是第一层一下所有节点中最后消去的，所以序列倒数第 s 个数字为 x，大于 s
假如 y 的父节点不是 x：
那么第一层一下最后一个消去的节点还是 x 的子节点（条件 1）。所以倒数第 s 个数字还是 x，大于 s
结论： 若第一层中存在最大数字 x 大于 s，则序列的倒数第 s 个数字必定为 x。
所以第二条也是成立的。
然后构造序列就很简单了最后 s-1 个数字都为 0，倒数第 s 个为 1...s，剩下为 1...n。
公式 ： s*n^(n-s-1)
不过当 s=n 的时候答案为 1 要另外处理，因为第一层下面没有东西了。

附本题代码
---------------------------------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

LL qmod(LL a,LL b){
    LL res=1ll;
    while(b){
        if(b&1) res=res*a%MOD;
        b>>=1;      a=a*a%MOD;
    }
    return res ;
}

int n,s;
LL solve(){
    if(n==s) return 1ll;
    return 1ll*s*qmod(n,n-s-1)%MOD;
}

int main(){
    int _ = 1,kcase = 0;
    while(~scanf("%d",&_)){
        while(_--){
            scanf("%d%d",&n,&s);
            printf("%lld\n",solve());  //在zoj不知为什么 %I64d 会出现PE的情况
        }
    }
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN

zoj

编码