文档介绍：2006年全国信息学冬令营讲座第1页/ 共21页数与图的完美结合-------浅析差分约束系统华中师大一附中冯威[摘要] 在面对多种多样的问题时,我们经常会碰到这样的情况:往往我们能够根据题目题面意思来建立一些简单的模型,但却面对这些模型无从下手。这时我们应该意识到,也许能够将这种模型与其他的模型之间搭起一座桥梁,使我们能够用更简单直接的方式解决它。这里我们介绍一种方法,它很好地将某些特殊的不等式组与图相联结,让复杂的问题简单化,将难处理的问题用我们所熟知的方法去解决,它便是差分约束系统。这里我们着重介绍差分约束系统的原理和其需要掌握的bellman-ford算法。然后通过zju1508和zju1420两道题目解析差分约束系统在信息学题目中的应用,并逐渐归纳解决这类问题的思考方向。[目录] ◆关键字·······························································································【2】◆ Bellman-ford算法············································································【2】◇算法简单介绍·················································································【2】◇算法具体流程················································································【2】◇例题一ZJU2008 ··············································································【4】◆差分约束系统·········&