【关键字】 图论模型、建立、转化 【摘要】 在近几年的信息学竞赛中,图论题目层出不穷。图论作为 一个新生的数学分支,相比其他数学分支来说,具有许多自有 的特性。利用图论解题,通常具有高效、简洁的便利。有了这 门工具,并不意味就能很好地解决问题,还在于我们能否熟练 地识别与建立一系列的图论模型。本文通过一些实例,简单地 介绍一下图论建模的方法。
输入文件的第一行为测试点个数(<= 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)。
[小结]
本题用到了差分约束系统的理论,在竞赛中,这样的系统并不多见,但是却可以巧妙的解决一些难题。这类题目的模型都不明显,需要一定的思考和转化。做这类题目,关键是要把题目中的约束条件表示为不等式,再把不等式转化为图的最短路或最长路模型。
算法合集之《浅谈图论模型... 27页 免费 图论模型的建立及转化方法 2页 5...第三部分主要讨论了在图论模型的转化中,应用得较为广泛的两种方 法:拆分转化和...
算法合集之《图论模型的建立与转化》_天文/地理_自然科学_专业资料。算法合集...第三部分主要讨论了在图论模型的转化中,应用得较为广泛的两种方 法:拆分转化和...
图论模型的建立与应用 37页 免费 算法合集之《图论模型的建... 12页 免费 算法合集之《浅谈图论模型... 9页 免费 图论模型的构建 41页 免费 算法合集之《...
图论模型的建立与应用 37页 免费 算法合集之《浅谈图论模型... 9页 免费 ...建立图论模型的目的和建立其它的数学模型一样,都是为了简化问题,突出要点,以 便...
算法合集之《浅谈图论模型... 27页 免费 图论的基本算法及应用 60页 2财富...图论模型为 平台挖掘问题 的性质 结语图论基本思想的精华 “模型 ” 建立模型 ...
算法合集之《数学模型的建立和选择》_IT/计算机_...我们就要想方设法将信 息原型对应到图论中的模型...信息原型的独特属性,并且 有效地在算法中加以应用. ...
算法合集之《浅谈网络流算法的应用》_IT/计算机_专业资料。算法合集之《浅谈...浅谈网络流算法的应用缺点:相对于其它图论算法来说,它的模型更加复杂,编程复杂度...
建立模型仿佛 图论的基本思想及方法 任恺 是为算法设计搭建一个平台, 接下来的... 算法合集之《浅谈图论模... 9页 免费 算法合集之《浅谈图论模... 27页 ...
图论模型的建立与应用 37页 免费 算法合集之《浅谈图论模型... 9页 免费喜欢此文档的还喜欢 图论模型在实际中的应用 66页 免费 图论的应用 13页 免费 图论 ...
热门文档