问题简述
有一些植物，每个植物携带有一定的资源（可正可负），且有一个攻击范围，可以保护攻击位置上的另一个植物。有一群僵尸从右向左进攻植物，僵尸不能走到植物的攻击范围...
|
|||||
|
经过几天努力终于做完了线性规划与网络流24题，同时对网络流和二分图的理解也上升到了一个新的高度。把所有题解发上来供大家参考，还请多多指教。 感谢ShingRay发现本文一个错误... 把问题抽象成图论问题，数学模型是求从S到T的两条不相交的路径，使得路径上点的权值之和最大。 费用流建模，首先拆点，把顶点i拆成i.a和i.b，i.a 与i.b之间连接一条费用为“好心值... 题目要求是删除权值之和最少的一些边，使得从1到N的最短路径变大。方法是求最短路径网络上的最小割集。首先求出从1到N的最短路径网络，方法是分别从1和N求单源最短路径，然后枚举每... 这道题正确的解法是构造网络，求网络最小费用最大流，但是模型隐藏得较深，不易想到。构造网络是该题的关键，以下面一个例子说明构图的方法和解释。 例如一共需要4天，四天需... 看过这道题，很容易想到用网络流的方法来构建问题模型。但是N<=5000，没有给出明确的边数限制使得我们不能从网络流下手。重新读题，注意到每个点邻接到的点都是按照一个顺序（自东... 这是一个网络最大流问题。读题发现有很明显的模型，入口和出口的通道容量都是1，内部通道没有容量限制，求从1到N最多通过的人数。 源为1，汇为N，把连接源和汇的通道建立为容量...
|
|
||||
|
Copyright © 2010 Beyond the Void - All Rights Reserved
|
|||||