阅读习惯

标签

NOI 2009 植物大战僵尸

问题简述

有一些植物,每个植物携带有一定的资源(可正可负),且有一个攻击范围,可以保护攻击位置上的另一个植物。有一群僵尸从右向左进攻植物,僵尸不能走到植物的攻击范围...

线性规划与网络流24题 解题报告

经过几天努力终于做完了线性规划与网络流24题,同时对网络流和二分图的理解也上升到了一个新的高度。把所有题解发上来供大家参考,还请多多指教。

感谢ShingRay发现本文一个错误...

NOIP2008 传纸条 费用流建模

把问题抽象成图论问题,数学模型是求从S到T的两条不相交的路径,使得路径上点的权值之和最大。

费用流建模,首先拆点,把顶点i拆成i.a和i.b,i.a 与i.b之间连接一条费用为“好心值...

AHOI 上学路线

题目要求是删除权值之和最少的一些边,使得从1到N的最短路径变大。方法是求最短路径网络上的最小割集。首先求出从1到N的最短路径网络,方法是分别从1和N求单源最短路径,然后枚举每...

NOI 2008 志愿者招募 employee

这道题正确的解法是构造网络,求网络最小费用最大流,但是模型隐藏得较深,不易想到。构造网络是该题的关键,以下面一个例子说明构图的方法和解释。

例如一共需要4天,四天需...

POI 2000 Skiers 滑雪队

看过这道题,很容易想到用网络流的方法来构建问题模型。但是N<=5000,没有给出明确的边数限制使得我们不能从网络流下手。重新读题,注意到每个点邻接到的点都是按照一个顺序(自东...

POI 1999 洞穴探险 Speleology

这是一个网络最大流问题。读题发现有很明显的模型,入口和出口的通道容量都是1,内部通道没有容量限制,求从1到N最多通过的人数。

源为1,汇为N,把连接源和汇的通道建立为容量...

Page 1 of 212