当前位置: 代码迷 >> 综合 >> 2311: [CEOI2016]D2T3 Router
  详细解决方案

2311: [CEOI2016]D2T3 Router

热度:89   发布时间:2023-10-29 10:17:09.0

做法指导自今年国家队队长CGH

本文由于我写的比较简略,所以一下参数系数什么加减1的操作我就先省略了

算法1

不妨考虑暴力建边。。
那么就是n2条边,然后最大代价就是2
期望得分9分

算法2

我们考虑建立中转站
然后我们先考虑建立n个中转站
然后每根号个点就连向一个中转站,然后每个中转站连向全部
这样无论代价还是边数都是nn
期望得分22分

算法3

我们考虑上一个算法,显然是是不够优秀的
我们发现,我们只是同一了第一排点的连线,但是第二排还是的连发还是十分暴力
于是我们不妨考虑对第二排点如法炮制,也弄一个中转站
于是我们就连两行K点,然后k2条边
同样的,我们的起点和终点都是n/k个连向一个点
然后这样的话,我们不难发现,当k是n的三分之二次方的时候最优
其实我也不知道为什么。。
然后这个期望得分48

算法4

我们发现,2排点似乎也不怎么够用啊
于是我们考虑弄出多排点
那么这种暴力连边的方法就要改一改了
这里写图片描述
我们可以对一层的点拆多n个,然后类似上图的连边,右边也是一样连,我这里就不写了
然后你就可以转化为两个子问题:就是让左边的n/2个都能对应到下面的n/2个终点
然后你就可以递归地分治了
我们来分析一波复杂度:
分治是只有log层的,然后每一层会多出2*n的边
于是T(n)=T(n/2)*2+2n
然后大概是是2nlogn+n
然后一个点的代价
如果它在第i层,那么就会有2^i个起点可以连接到它,但是却只有n/2^i个终点可以连接到它了,于是代价最多就是2n的

这个的话虽然代价很小,但是边数很多

算法5

也就是最终的算法了
考虑到算法4的代价特别小,边数特别多
于是我们可以使用类似于算法1或者2的方法优化一下
根据乱搞,我们得出当我们对起点和终点每4个点合并一下的时候是最优的
复杂度分析我就不写了。。
大家大概算一下就好了,是可以过的。。

  相关解决方案