BZOJ 4089:[Sdoi2015]graft(SDOI 2015 Round 2 Day 2)

2015年6月18日4790

别人家的神选系列,我只会做这道题QAQ

题目描述:

给定一颗树,加上k条边,将n个点染色,相邻两点不同,记颜色为i的又ti个,求$$\frac{\sum_{i=1}^{n} \frac{ti}{i}}{1+p\sum_{i=1}^{n}iti}$$(擦擦擦我今天才知道能用Tex公式QAQ害得我以前写的好辛苦QAQ)的最大值。(k<=2)
这是分数规划嘛,那么我们就可以二分答案x。然后我们每种颜色的值就变为$\frac{1}{i}-pxi$啦,然后就可以直接上DP啦。dp我们每个点记录3个值:该子树的最大值,该子树取最大值时根节点的颜色,不取该颜色时该子树的最大值。然后我们就能解决树的情况了

加上两条边也很简单,可以直接枚举一边端点然后限制另一端点无法取该值即可

由于颜色最多只有$log_2 n$种,所以时间复杂度为$O(nklog_2 n log p) $实验证明以上一次的答案作为这次的答案收敛速度比二分快

CODE:

 

%d 博主赞过: