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

钱桥


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

谢谢


赞助商链接
相关文章:
无锡市钱桥中学
无锡市钱桥中学_专业资料。无锡市钱桥中学 2013~2014 学年第二学期第 13、14 周工作安排 5 月 11 日-5 月 24 日 一、全校性工作 1、继续开展党的群众...
[案例1] 钱桥纺织厂为国有企业,下设办公室、行政科、会...
[案例1] 钱桥纺织厂为国有企业,下设办公室、行政科、会计科、档案科等职能科室。 2005年7月,经上级主管单位任命,会计科长甲的丈夫乙担任该厂厂长。同月,甲的...
安徽省枞阳县钱桥初级中学九年级语文下册 15 枣儿教案 ...
安徽省枞阳县钱桥初级中学九年级语文下册 15 枣儿教案 新人教版_语文_初中教育_教育专区。15 枣儿教学目标 知识目标 1.了解剧情,了解我国在现代化进程中人们生存...
2015-2016学年江苏省无锡市钱桥中学八年级(下)第一次月考
2015-2016学年江苏省无锡市钱桥中学八年级(下)第一次月考_其它课程_小学教育_教育专区。2015-2016 学年江苏省无锡市钱桥中学八年级(下)第一次月考 2015-2016 ...
安徽省枞阳县钱桥初级中学高中语文 人间三月天作文素材
安徽省枞阳县钱桥初级中学高中语文 人间三月天作文素材_高考_高中教育_教育专区。安徽省枞阳县钱桥初级中学高中语文 人间三月天作文素 材三月散暖意,蛙鸣百花开。闻...
2016-2017学年江苏省无锡市钱桥中学七年级数学上12月月...
2016-2017学年江苏省无锡市钱桥中学七年级数学上12月月考试卷.doc_数学_高中教育_教育专区。2016-2017 学年江苏省无锡市钱桥中学七年级(上)月考数 学试卷(12 ...
2015-2016学年安徽省枞阳县钱桥初级中学九年级政治上册...
2015-2016学年安徽省枞阳县钱桥初级中学九年级政治上册教案《我们的共同理想》.doc - 教学目标 (一)知识目标 1.说出全面建设小康社会的奋斗目标; 2.能分析我们的...
钱桥镇学前教育三年行动计划
钱桥镇学前教育三年行动计划 实施情况汇报一、学前教育发展状况: 我镇现有公办独立幼儿园两所, 附属幼教点三所, 民办 A 类看护 点一所,B 类看护点三所。公办...
钱桥镇环保意识及环保状况调查研究
淮阴工学院 “思政课”社会实践报告 题目:钱桥镇环保意识及环保状况调查与研究 学院:电子与电气工程学院 班级:测控技术与仪器__姓名:吴景生___学号:1101203202...
钱桥镇钱白公路钱桥段新路基工程实施方案的说明
钱桥镇钱白公路钱桥段新路基工程 实施方案的说明 一、概况 钱桥白湖公路,起于钱桥境内庐十线,终于白湖乡白会 路,全长 10.12 公里,途径钱桥、白湖两乡镇,中...
更多相关标签: