下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 高二下期5月15日NOIP图论基本算法测试题

高二下期5月15日NOIP图论基本算法测试题.doc

高二下期5月15日NOIP图论基本算法测试题

faint
2018-09-07 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《高二下期5月15日NOIP图论基本算法测试题doc》,可适用于工程科技领域

NOIP图论基本算法测试题一ProblemA最优乘车(travelpas)H城是一个旅游胜地每年都有成千上万的人前来观光。为方便游客巴士公司在各个旅游景点及宾馆饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发依次途经若干个巴士站最终到达终点巴士站。一名旅客最近到H城旅游他很想去S公园游玩但如果从他所在的饭店没有一路已士可以直接到达S公园则他可能要先乘某一路巴士坐几站再下来换乘同一站台的另一路巴士,这样换乘几次后到达S公园。现在用整数,,…N给H城的所有的巴士站编号约定这名旅客所在饭店的巴士站编号为…S公园巴士站的编号为N。写一个程序帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换车的次数最少。输入(travelin)数据的第一行有两个数字M和N(<=M<=<N<=)表示开通了M条单程巴士线路总共有N个车站。从第二行到第M行依次给出了第条到第M条巴士线路的信息。其中第i行给出的是第i条巴士线路的信息从左至右按运行顺序依次给出了该线路上的所有站号,相邻两个站号之间用一个空格隔开。当M=N=是结束输出(travelout)输出数据只有一行。如果无法乘巴士从饭店到达S公园则输出"N"否则输出你的程序所找到的最少换车次数换车次数为表示不需换车即可到达•样例输入样例输出ProblemB运送物资(Conveypas)X国发生了内战。起义军得到了广大人民的支持。在一次战役中反动军队结集了大量兵力围攻起义军的主堡W城。为支援前线后方各个供给基地城市纷纷准备将物资运往W城。各基地及W城之间有的有公路相连。这就是说有的基地不能将物资一次运到W城必须通过中途的转运。根据每条公路的长短和运送物资的多少运送中将会有不同程度的损耗。现假设每条公路都有一个损耗系数表示经过这条公路的物资总量与消耗量的比值。另外为保证物资安全到达每个基地都会等所有要通过该基地转运的物资到齐后连同本基地的物资一起运到下一站。也就是说从任何一个基地出发都只能将物资运往另一基地但允许多个基地的物资运往同一基地。请编程预定出每个基地的运输路线使到达W城的总物资最大。输入:{conveyin}第一行给出两个整数n(<=n<=)与m。其中n表示有n个基地(编号为到n)与一个W城(编号为n)m表示有m条公路。第二行给出了n个正整数(正整数<=),表示编号为到n的基地要运送的物资数量。接下来m行描述了m条公路的情况每一行有个数如 表示号城市与号城市之间有一条公路连接其损耗系数为。注意:数据给出的公路网保证每个基地都能将物资运到W城。输出:{conveyout}仅一行即运到W城的最大物资数(结果保留两位小数)。样例输入样例输出ProblemC公路建设(roadpas)A国是一个新兴的国家有N个城市分别编号为,…N。政府想大搞公路建设提供了优惠政策:对于每一个投资方案的预计总费用政府负担并且允许投资的公司对过往的汽车收取连续年的养路费。世界各地的大公司纷纷投资并提出了自己的建设方案他们的投资方案包括这些内容:公路连接的两座城市的编号预计的总费用(假设他们的预计总师准确的)。你作为A国公路规划局的总工程师有权利决定每一个方案是否接受。但是政府给你的要求是:()要保证各个城市之间都有公路直接或间接相连。()因为是新兴国家政府的经济实力还不强,政府希望负担最少的费用。()因为大公司并不是同时提出方案政府希望每接到一个方案就可以知道当前需要负担的最小费用和接受的投资方案以便随时开工。注意:A国一开始是没有公路的,A国的城市数目N<=投资的方案总数M<=。输入文件:(Roadin)第行有两个数字:N、M第行到第M行给出了各个投资方案第i行的方案编号为i编号小的方案先接到一个方案占一行每行有个数字分别是连接的两个城市编号a、b和投资的预计总费用cost。输出文件:(Roadout)输出文件共有M行。每一行的第一个数字是当前政府需要负担的最少费用(保留位小数)后面是X个数字表示当前政府接受的方案的编号不要求从小到大排列。但如果此时接受的所有投资方案不能保证政府的第一条要求那么这一行只有一个数字【样例】RoadinRoadoutProblemD乘车路线(roadspas)编号为N的N座城镇用若干双向行驶的道路相连每条道路上均有两个参数:道路长度(length)和在该条道路上行驶的费用(cost)。BOB准备从城镇出发到达城镇N但他目前只有W的钱为此你需要帮助他寻找一条从城镇到城镇N在他能支付的前提下的一条最短路线。输入:(roadsin)WNK(N为城镇数目<=N<=K为道路条数<=K<=,W为钱的数目<=w<=)随后的K行每行为一条道路的信息包含个数值(S,D,L,T)其中S为源城镇D为目标城镇L为道路长度T为所需支付用。(<=S,D<=N,<=L<=,<=T<=)输出:(roadsout)输出最短长度若无解则输出“NO”样例:roadsinroadsout

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/5

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利