当前位置:首页 >> 学科竞赛 >>

钱桥


APIO 试题讨论
道路费用

题目描述

? ? ? ? ? ? ?

n个城镇,每个城镇有Pi的人 m条道路,每条道路的单位费用为Cj(互不相等) 新建k条道路,单位费用由你决定 一条道路收取的费用为经过人数乘以单位费用 由你挑选出一些道路构成费用的“最小生成树” 所有人都要到1号城镇集合 你的目标是让新

建的k条边收取最多的费用

数据规模

? Part 1 : n<=10, m<=20, k=1 ? Part 2 : n<=30, m<=50, k<=10 ? Part 3 : n<=1000, m<=5000, k<=10 ? Part 4 : n<=100000, m<=300000, k<=15 ? Part 5 : n<=100000, m<=300000, k<=20

得分情况

? 100分:王康宁 ? 95分:郁东风 ? 90分:叶德铭 ? 70分:钟皓曦 ? 60:王子辰 等7人 ? 平均分:11.60

解题思路

算法一:向最小生成树中逐一加边,替换原路径上 权值最大的边。当k>1时,不能保证正确性!举例:

时间复杂度:O(k*m) 期望的分:15分~?

解题思路

算法二:暴力枚举使用哪些边,让选中的边尽可能大

共2k种情况,对于每一种情况: Step 1:构造最终的最小生成树,优先使用选中的边 Step2:确定选中边的权值——经过它的最小值
时间复杂度O(m*logm + 2k*m*k) 期望的分:35分

解题思路

算法三:先缩点,再通过算法二处理

选中的边为0~20条,Step 1中构造的最小生成树有n-1条。 结论:有很多点是一定“粘”在一起的。怎样缩点? 初始化构造最小生成树,其中,优先使用k条边。 形成的k+1个连通块可分别缩为一个点。

解题思路
初始化构造最小生成树(优先使用k条边) 形成的k+1个连通块可分别缩为一个点 再求这k+1个点的最小生成树,(不使用k条边) 得到k+1个点,k条边的一张图 通过算法二求解这张图 时间复杂度:O(m*logm + 2k*k2) 期望得分:90~100分 (数据为阶梯分布)

谢谢


相关文章:
江苏中小城镇化发展动力机制研究——以无锡市钱桥镇为...
江苏中小城镇化发展动力机制研究 ——以无锡市钱桥镇为例 151150075 郁一帆联系方式:15061813731 摘要:钱桥镇地处江苏省无锡市,是以冶金、焊管产业为支柱的工业强镇...
江苏钱桥金属制品交易中心项目申请报告
53 -i- 江苏钱桥金属制品交易中心项目申请报告 第一章 项目基本情况 1.1 项目概况(1)项目名称:江苏钱桥金属制品交易中心 (2) 建设地点: 江苏钱桥金属制品交易...
钱桥初中艺术展演活动方案
(2) 艺术表演奖: 歌手和书画作品以及舞蹈分设一等奖、 二等奖、 三等奖。 钱桥初中 2012 年 3 月 31 日 时间:4 月中旬 时间: 4 月中旬 ...
2016年财经法规重点
档案科长与会计科长张红共同在会计档案销毁清册上签字,并进行了监销 D 会计科长张红指定出纳张芳兼管会计档案保管工作 答案: 2-4 钱桥纺织厂为国有企业,下设...
2015年度无锡钱桥钢管有限公司销售收入与资产数据报告_...
2015年度无锡钱桥钢管有限公司销售收入与资产数据报告_调查/报告_表格/模板_实用文档。BY: 2016 年 D 系列报告 : 企业数据报告 出品机构:中国产业洞察网 www.51...
记铜陵市枞阳县钱桥镇维多利亚婚纱婚庆策划师、鼓书艺...
记铜陵市枞阳县钱桥镇维多利亚婚纱婚庆策划师、鼓书艺人吴福东_随笔_生活休闲。路漫漫其修远兮,民间奇才、鼓书艺人吴福东是枞阳家乡人民的骄傲,祝福他的明天会更好!...
无锡市惠山区钱桥街道晴山蓝城社区基层调研汇报
无锡市惠山区钱桥街道晴山蓝城社区基层调研汇报_工作总结/汇报_总结/汇报_应用文书。钱桥街道晴山蓝城社区基层建设工作汇报尊敬的秦副主席,各位领导: 大家上午好! 首...
“钱桥杯”篮球比赛策划书
芜湖市公路管理局“钱桥杯”篮球比赛 策划书一、活动目的:为迎接新中国成立 65 周年,丰富活跃项目参建人员 的娱乐文化体育生活, 加强项目参建人员之间相互沟通及团队...
2015年度无锡钱桥带钢有限公司销售收入与资产数据报告_...
2015年度无锡钱桥带钢有限公司销售收入与资产数据报告_调查/报告_表格/模板_实用文档。BY: 2016 年 D 系列报告 : 企业数据报告 出品机构:中国产业洞察网 www.51...
安徽省枞阳县钱桥初级中学高中语文 生命的代价作文素材
安徽省枞阳县钱桥初级中学高中语文 生命的代价作文素材_高考_高中教育_教育专区。安徽省枞阳县钱桥初级中学高中语文 生命的代价作文素材 生命,她是一个多么美丽的...
更多相关标签:
无锡钱桥 | 奉贤钱桥 | 钱桥镇 | 钱桥中学 | 前桥 | 钱桥国际大酒店 | 钱桥街道 | 枞阳钱桥 |