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

钱桥


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分 (数据为阶梯分布)

谢谢


相关文章:
2016无锡市初三钱桥第一次月考卷_图文
2016无锡市初三钱桥第一次月考卷_初三英语_英语_初中教育_教育专区。2016无锡市初三钱桥第一次月考卷 2015-2016 学年九年级英语阶段测试卷(试卷满分为 110 分)...
钱桥镇人文地理特征研究报告
钱桥镇人文地理特征研究报告第一部分:地理概况钱桥镇,地理坐标约为(31°N ,117°E) ,位于安庆市枞阳县北部,与枞阳县城的距 离约为 41 公里,东边是白湖乡,南...
钱桥初中组织学生参观安庆市青少年思想教育基地
为激发学生爱国主义热情,进一步加强爱国主义信念教育,更好 的教育青少年知党、爱党、听党话、跟党走,11 月 20 日上午,钱桥 初中团委组织各班团支部书记和学生会...
无锡市惠山区钱桥街道晴山蓝城社区基层调研汇报
无锡市惠山区钱桥街道晴山蓝城社区基层调研汇报_工作总结/汇报_总结/汇报_应用文书。钱桥街道晴山蓝城社区基层建设工作汇报尊敬的秦副主席,各位领导: 大家上午好! 首...
(强烈推荐)江苏钱桥金属制品交易中心项目可行性研究报告
(强烈推荐)江苏钱桥金属制品交易中心项目可行性研究报告_调查/报告_表格/模板_实用文档。研究报告,项目建议书,项目建设,项目论证,项目可行性研究报告,可行性研究报告...
钱桥钢管交易中心悬挑脚手方案
钱桥钢管交易中心商务办公楼工程悬挑脚手施工方案§1、工程概况 钱桥钢管交易中心商务办公楼工程总建筑面积为 39572m2,建筑层数 为 25F, 首层层高为 6m, 三层层高为...
江苏省无锡市惠山钱桥2013-2014学年七年级上期末考试数...
江苏省无锡市惠山钱桥2013-2014学年七年级上期末考试数学试题及答案【苏科版】_数学_初中教育_教育专区。江苏省无锡市惠山钱桥2013-2014学年七年级上期末考试数学试...
钱桥镇钱白公路钱桥段新路基工程实施方案的说明
钱桥镇钱白公路钱桥段新路基工程 实施方案的说明 一、概况 钱桥白湖公路,起于钱桥境内庐十线,终于白湖乡白会 路,全长 10.12 公里,途径钱桥、白湖两乡镇,中...
钱桥社区整治计划
钱桥社区巡防队工作计划 钱桥社区巡防队工作计划 巡防队(2011 年 9 月-2011 年 10 月) 为进一步规范社区秩序, 改善社区环境, 提升社区形象, 钱桥社区城管工作...
钱桥镇钱桥村党总支事迹材料
钱桥钱桥村党总支事迹材料 钱桥钱桥村党总支事迹材料在钱桥镇党委的坚强领导下,钱桥村党总支按照“围绕经济抓党 建、抓好党建促发展”的工作思路,以创建“五个...
更多相关标签: