文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 算法合集之《浅谈图论模型的建立与应用》
侵权投诉

算法合集之《浅谈图论模型的建立与应用》

【关键字】 图论模型、建立、转化 【摘要】 在近几年的信息学竞赛中,图论题目层出不穷。图论作为 一个新生的数学分支,相比其他数学分支来说,具有许多自有 的特性。利用图论解题,通常具有高效、简洁的便利。有了这 门工具,并不意味就能很好地解决问题,还在于我们能否熟练 地识别与建立一系列的图论模型。本文通过一些实例,简单地 介绍一下图论建模的方法。

输入文件的第一行为测试点个数(<= 20)。每组测试数据的第一行为24个整数表示R0,R1,..., R23(RI≤1000)。接下来一行是N,表示申请者数目(0≤N≤1000),接下来每行包含一个整数tI (0≤tI≤23)。两组测试数据之间没有空行。

输出

对于每个测试点,输出只有一行,包含一个整数,表示需要出纳员的最少数目。如果无解,你应当输出“No Solution”。

[分析]

初看本题,很容易使人往贪心、动态规划或网络流这些方面思考,但这些算法对于本题都无能为力。

由于本题的约束条件很多,为了理清思路,我们先把题目中的约束条件用数学语言表达出来。设S[i]表示0~i时刻雇佣出纳员的总数,Wi表示在时刻i开始工作的申请者的人数。那么我们可以将题目中的约束条件转化为下面的不等式组:

0≤S[i]-S[i-1]≤Wi 0≤i≤23 S[i]-S[i-8]≤ Ri 8≤i≤23

S[23]+S[i]-S[i+16]≤R 0≤i≤7i

这样的不等式组,不禁使我们想到了差分约束系统。对于每条不等式 S[i]-S[j]≤K,从顶点j向顶点i引一条权值为K的有向边。我们要求的S[23]的最小值,只要求顶点0到顶点23的最短路。但是注意上面第三条不等式:它包含三个未知数,无法在图中表示为边的关系。

思考到这一步,似乎陷入了僵局。难道本题不能用差分约束系统解决吗?不,我们还需要一些转化。退一步海阔天空,如果把S[23]作为未知数,那是肯定做不下去的。但是如果把S[23]作为已知数,那么第三条不等式就只有两个未知数S[i],S[i+16],我们从顶点i+16向顶点i(0≤i≤7)引一条权值为Ri-S[23]的边。那么,该不等式组可以完全转化为一个有向图,未知数S[i]的解,就是图中顶点0到顶点i的最短路。而当图中存在负权回路时,不等式组无解。

上面的解法是把S[23]当成了已知数,而实际上S[23]不但是未知的,而且正是我们要求的。怎么办?我们可以用二分法枚举S[23]的值,逐步缩小范围,用迭代法判断是否存在负权回路(判定可行性)。如果当S[23]取到N仍不可行,则输出“No Solution”,否则输出S[23]的最小值。时间复杂度为O(243*log2N)。

[小结]

本题用到了差分约束系统的理论,在竞赛中,这样的系统并不多见,但是却可以巧妙的解决一些难题。这类题目的模型都不明显,需要一定的思考和转化。做这类题目,关键是要把题目中的约束条件表示为不等式,再把不等式转化为图的最短路或最长路模型。

上一页第4页

你可能喜欢

  • 图论算法
  • 算法竞赛
  • 图论及其应用
  • 遗传算法应用
  • 历年数学建模优秀论文
  • 图论论文

热门文档

相关文档

  • 算法合集之《图论模型的建立与转化》

    算法合集之《浅谈图论模型... 27页 免费 图论模型的建立及转化方法 2页 5...第三部分主要讨论了在图论模型的转化中,应用得较为广泛的两种方 法:拆分转化和...

  • 算法合集之《图论模型的建立与转化》

    算法合集之《图论模型的建立与转化》_天文/地理_自然科学_专业资料。算法合集...第三部分主要讨论了在图论模型的转化中,应用得较为广泛的两种方 法:拆分转化和...

  • 图论模型的建立

    图论模型的建立与应用 37页 免费 算法合集之《图论模型的建... 12页 免费 算法合集之《浅谈图论模型... 9页 免费 图论模型的构建 41页 免费 算法合集之《...

  • 图论模型的建立与转化

    图论模型的建立与应用 37页 免费 算法合集之《浅谈图论模型... 9页 免费 ...建立图论模型的目的和建立其它的数学模型一样,都是为了简化问题,突出要点,以 便...

  • 算法合集之《图论的基本思想及方法》

    算法合集之《浅谈图论模型... 27页 免费 图论的基本算法及应用 60页 2财富...图论模型为 平台挖掘问题 的性质 结语图论基本思想的精华 “模型 ” 建立模型 ...

  • 算法合集之《数学模型的建立和选择》

    算法合集之《数学模型的建立和选择》_IT/计算机_...我们就要想方设法将信 息原型对应到图论中的模型...信息原型的独特属性,并且 有效地在算法中加以应用. ...

  • 算法合集之《浅谈网络流算法的应用》

    算法合集之《浅谈网络流算法的应用》_IT/计算机_专业资料。算法合集之《浅谈...浅谈网络流算法的应用缺点:相对于其它图论算法来说,它的模型更加复杂,编程复杂度...

  • 算法合集之《图论的基本思想及方法》

    建立模型仿佛 图论的基本思想及方法 任恺 是为算法设计搭建一个平台, 接下来的... 算法合集之《浅谈图论模... 9页 免费 算法合集之《浅谈图论模... 27页 ...

  • 图论在给水调度模型中的应用

    图论模型的建立与应用 37页 免费 算法合集之《浅谈图论模型... 9页 免费喜欢此文档的还喜欢 图论模型在实际中的应用 66页 免费 图论的应用 13页 免费 图论 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email