重建计划 解题报告.pdfVIP

重建计划 解题报告 江苏苏州中学 宋文杰 1，题目描述 【问题描述】 X 国遭受了地震的重创, 导致全国的交通近乎瘫痪，重建家园的计划迫在眉 睫。X 国由N 个城市组成, 重建小组提出，仅需建立N -1 条道路即可使得任意 两个城市互相可达。于是，重建小组很快提出了一个包含N -1 条道路的方案，并 满足城市之间两两可达，他们还计算评估了每条道路e 建设之后可以带来的价值 v(e) 。 由于重建计划复杂而艰难，经费也有一定限制。因此，政府要求第一期重 建工程修建的道路数目为k 条，但需满足L ≤ k ≤ U, 即不应少于L 条，但不超过 U 条。同时，为了最大化利用率，要求建设的这些道路恰好组成一条简单路径， 即所建设的k 条路径可以构成一个排列e = (p , q ), e = (p , q )……e = (p , q ), 1 1 1 2 2 2 k k k 对于 1 ≤ i k, 有(q = p +1) 。 重建小组打算修改他们的原有方案以满足要求， i i 即在原有的N -1 条道路中寻找一条路径S 作为新的方案，使得新方案中的道路平 均价值： 最大。这里v(e)表示道路e 的价值，|S |表示新方案中道路的条数。请你帮助 重建小组寻找一个最优方案。 注: 在本题中L 和U 的设置将保证有解。 【输入文件】 第一行包含一个正整数N，表示X 国的城市个数。 第二行包含两个正整数 L 、U，表示政府要求的第一期重建方案中修建道路 数的上下限。 接下来的N-1 行描述重建小组的原有方案，每行三个正整数a 、 i b 、v ，分别表示道路(a, b )，其价值为v 。其中城市由1…N 标号。 i i i i i 【输出文件】 一行，为一个实数AvgValue ，即最大平均价值。小数点后保留三位。 【输入样例】 4 2 3 1 1 2 1 1 3 2 1 4 3 【输出样例】 2.500 【数据规模和约定】 100% 的数据中N≤100000 ； 2，初步分析 如果只是一条链的话，我们可以有O(n) 的算法： 设sum[i]=sum[i-1]+A[i]，设f[x]为以x 为结尾的链的平均值的最大值。 sum[x ] sum[i] f [x ] max   x Uix L  x i  这个很容易利用凸性优化来做到O(n) 。 3，树的算法 联想到关于树的算法：点剖分。 我们首先为一棵无根树选择一个根，然后把它删除得到若干棵子树。 分治： 我们先递归计算每一颗子树的所有路径中的最大平均价值。 合并： 然后我们计算所有经过根节点的路径的最大平均价值。 我们先把所有子树T1 ，T2 ……Tk 按深度从小到大排一下序。 然后对每一个棵都进行一次dfs，得到一个s[Ti][j]表示Ti 为根子树中，长度为j 的路径的权值和的最大值。 接着，我们逐个合并子树们。 对于两个子树Ti 、Tj 我们有两个步骤： 第一、 需要计算经过根，并且链的两个端点分别在这两棵子树中的最大平均 价值。 第二、 把s[Ti][]和s[Tj][] 的值合并了。 其中，第二步很容易，我们只需要O(|Ti |)的复杂度