Beyond the Void

问题简述

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

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

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

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

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

几点说明

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

问题一览

把问题抽象成图论问题，数学模型是求从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 »

题目要求是删除权值之和最少的一些边，使得从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 »

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

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

设雇佣第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)。

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

所以，答案为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，恰好就像网络流中除了源点和汇点的顶点都满足流量平衡。每个正的变量相当于流入该顶点的流量，负的变量相当于流出该顶点的流量，而正常数可以看作来自附加源点的流量，负的常数是流向附加汇点的流量。因此可以据此构造网络，求出从附加源到附加汇的网络最大流，即可满足所有等式。而我们还要求最小，所以要在X变量相对应的边上加上权值，然后求最小费用最大流。

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

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

Read the rest of this entry »