CF814E An unavoidable detour for home

An unavoidable detour for home

Solution

由最短路唯一,不难发现以下性质:

1、原图可以通过对于$1$号点的最短路长度分层,成一棵树的形式,每一层的最短路长度相同。

2、剩下的边只能在树的同层内的点加。

3、由于要求对于$i>j$有$dis_i>dis_j$,所以每一层是一段区间。

于是,我们就可以$DP$了。显然有一个暴力的做法,$f[i][pre_1][pre_2][now_1][now_2]$表示上一层剩下的度数为$1$的点有$pre_1$个,度数为$2$的点有$pre_2$个。这一层的对应分别有$now_1,now_2$个。转移讨论一下$i$号点的连边情况。当$pre_1=pre_2=0$时,这一层就填完了,该填到下一层。

显然是可以通过预处理同层里的方案数直接每层转移。注意到度数为$2$的点的方案数要提前除$2$。

同时注意到,数据范围只有$50$,所以好写$n^5$暴力就可以愉快通过了。真好写

发表评论

电子邮件地址不会被公开。 必填项已用*标注