Page 1 of 212

NOI 2009 植物大战僵尸

NOI 18 Comments »1,180 views

问题简述

有一些植物,每个植物携带有一定的资源(可正可负),且有一个攻击范围,可以保护攻击位置上的另一个植物。有一群僵尸从右向左进攻植物,僵尸不能走到植物的攻击范围内。任务是求一个进攻方案,使得僵尸获得的资源尽可能多。 Read the rest of this entry »

标签:, , ,

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

競賽題解 18 Comments »2,316 views

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

感谢ShingRay发现本文一个错误,现已修正。

BYVoid原创 线性规划与网络流24题_解题报告Ver 2 (48KB)

另外附上 线性规划与网络流24题 (1.90MB) 感谢王晓东老师给我们提供这么多好题。

几点说明

  1. 本题解提供所有问题的解析和大部分问题的C++程序源代码,以及个别数据的勘误。
  2. 本题解只讨论问题的分析和建模,具体的实现参照代码。代码中所有网络最大流算法均用Dinic实现。
  3. 读者应具备图论、最短路径、网络流的基础知识,并掌握至少一种网络最大流和最小费用最大流的算法。
  4. 建议读者在阅读题解前先进行充分的思考,确认无法独立解决后再看题解。
  5. 问题8 机器人路径规划问题 是个经典难题,暂时还未解决,欢迎大家讨论。
  6. 本题解系个人原创,请勿商业转载,非商业转载请注明来源。

问题一览

问题编号 问题名称 问题模型 转化模型
1 飞行员配对方案问题 二分图最大匹配 网络最大流
2 太空飞行计划问题 最大权闭合图 网络最小割
3 最小路径覆盖问题 有向无环图最小路径覆盖 网络最大流
4 魔术球问题 有向无环图最小路径覆盖 网络最大流
5 圆桌问题 二分图多重匹配 网络最大流
6 最长递增子序列问题 最多不相交路径 网络最大流
7 试题库问题 二分图多重匹配 网络最大流
8 机器人路径规划问题 (未解决) 最小费用最大流
9 方格取数问题 二分图点权最大独立集 网络最小割
10 餐巾计划问题 线性规划网络优化 最小费用最大流
11 航空路线问题 最长不相交路径 最小费用最大流
12 软件补丁问题 最小转移代价 最短路径
13 星际转移问题 网络判定 网络最大流
14 孤岛营救问题 分层图最短路径 最短路径
15 汽车加油行驶问题 分层图最短路径 最短路径
16 数字梯形问题 最大权不相交路径 最小费用最大流
17 运输问题 网络费用流量 最小费用最大流
18 分配问题 二分图最佳匹配 最小费用最大流
19 负载平衡问题 最小代价供求 最小费用最大流
20 深海机器人问题 线性规划网络优化 最小费用最大流
21 最长k可重区间集问题 最大权不相交路径 最小费用最大流
22 最长k可重线段集问题 最大权不相交路径 最小费用最大流
23 火星探险问题 线性规划网络优化 最小费用最大流
24 骑士共存问题 二分图最大独立集 网络最小割
标签:, , , ,

NOIP2008 传纸条 费用流建模

競賽題解 12 Comments »922 views

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

费用流建模,首先拆点,把顶点i拆成i.a和i.b,i.a 与i.b之间连接一条费用为“好心值”,容量为1的有向边,特殊地,左上角和右下角两个节点拆分后点内边容量设为2,因为我们要找两条不相交路径。i右边和下边的节点j,连接一条(i.b,j.a)费用为0,容量为1的有向边。

求最大费用最大流即可,费用流值就是要求的结果。比动态规划运行得快,空间占用少。
Read the rest of this entry »

标签:, , ,

AHOI 上学路线

競賽題解 6 Comments »176 views

题目要求是删除权值之和最少的一些边,使得从1到N的最短路径变大。方法是求最短路径网络上的最小割集。首先求出从1到N的最短路径网络,方法是分别从1和N求单源最短路径,然后枚举每条边,如果边(a,b)满足dis(1,a) + w(a,b) + dis(b,N) = dis(1,N) ,则(a,b)是最短路径网络上的(有向)边。

接下来求从1到N的网络最大流,即可求出最小割集。由于是求任意一个最小割集,所以只需遍历一边残余网络,S集合与T集合之间的边,就是一个最小割集。
Read the rest of this entry »

标签:, , ,

NOI 2008 志愿者招募 employee

NOI 21 Comments »2,139 views

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

例如一共需要4天,四天需要的人数依次是4,2,5,3。有5类志愿者,如下表所示:

种类 1 2 3 4 5
时间 1-2 1-1 2-3 3-3 3-4
费用 3 4 3 5 6

设雇佣第i类志愿者的人数为X[i],每个志愿者的费用为V[i],第j天雇佣的人数为P[j],则每天的雇佣人数应满足一个不等式,如上表所述,可以列出

P[1] = X[1] + X[2] >= 4

P[2] = X[1] + X[3] >= 2

P[3] = X[3] + X[4] +X[5] >= 5

P[4] = X[5] >= 3

对于第i个不等式,添加辅助变量Y[i] (Y[i]>=0) ,可以使其变为等式

P[1] = X[1] + X[2] – Y[1] = 4

P[2] = X[1] + X[3] – Y[2] = 2

P[3] = X[3] + X[4] +X[5] – Y[3] = 5

P[4] = X[5] – Y[4] = 3

在上述四个等式上下添加P[0]=0,P[5]=0,每次用下边的式子减去上边的式子,得出

① P[1] – P[0] = X[1] + X[2] – Y[1] = 4

② P[2] – P[1] = X[3] – X[2] -Y[2] +Y[1] = -2

③ P[3] – P[2] = X[4] + X[5] – X[1] – Y[3] + Y[2] =3

④ P[4] – P[3] = – X[3] – X[4] + Y[3] – Y[4] = -2

⑤ P[5] – P[4] = – X[5] + Y[4] = -3

观察发现,每个变量都在两个式子中出现了,而且一次为正,一次为负。所有等式右边和为0。接下来,根据上面五个等式构图。

  • 每个等式为图中一个顶点,添加源点S和汇点T。
  • 如果一个等式右边为非负整数c,从源点S向该等式对应的顶点连接一条容量为c,权值为0的有向边;如果一个等式右边为负整数c,从该等式对应的顶点向汇点T连接一条容量为c,权值为0的有向边。
  • 如果一个变量X[i]在第j个等式中出现为X[i],在第k个等式中出现为-X[i],从顶点j向顶点k连接一条容量为∞,权值为V[i]的有向边。
  • 如果一个变量Y[i]在第j个等式中出现为Y[i],在第k个等式中出现为-Y[i],从顶点j向顶点k连接一条容量为∞,权值为0的有向边。

构图以后,求从源点S到汇点T的最小费用最大流,费用值就是结果。

根据上面的例子可以构造出如下网络,红色的边为每个变量X代表的边,蓝色的边为每个变量Y代表的边,边的容量和权值标已经标出(蓝色没有标记,因为都是容量∞,权值0)。

noi_employee_1

在这个图中求最小费用最大流,流量网络如下图,每个红色边的流量就是对应的变量X的值。

noi_employee_2

所以,答案为4*3+2*3+3*6=36。

上面的方法很神奇得求出了结果,思考为什么这样构图。我们将最后的五个等式进一步变形,得出以下结果

① – X[1] – X[2] + Y[1] + 4 = 0

② – X[3] + X[2] + Y[2] – Y[1] – 2 = 0

③ – X[4] – X[5] + X[1] + Y[3] – Y[2] + 3 = 0

④ X[3] + X[4] – Y[3] + Y[4] – 2 = 0

⑤ X[5] – Y[4] – 3 = 0

可以发现,每个等式左边都是几个变量和一个常数相加减,右边都为0,恰好就像网络流中除了源点和汇点的顶点都满足流量平衡。每个正的变量相当于流入该顶点的流量,负的变量相当于流出该顶点的流量,而正常数可以看作来自附加源点的流量,负的常数是流向附加汇点的流量。因此可以据此构造网络,求出从附加源到附加汇的网络最大流,即可满足所有等式。而我们还要求noi_employee_3最小,所以要在X变量相对应的边上加上权值,然后求最小费用最大流

我写的是朴素的SPFA算法求增广路的最小费用流算法,可以在题目时限内通过所有测试点。

在NOI的现场上,该题得分的平均分12.56,只有高逸涵大牛拿到了满分。不能不说这是一道难题,难就难在抽象出问题的数学模型,设计有效的算法。而信息学竞赛正朝着这个方向发展,数学建模将是解决问题的共同关键步骤。

Read the rest of this entry »

标签:, , , ,
20 queries. 0.500 seconds. Designed by NattyWP .
Images by desEXign.