2006年全国信息学冬令营讲座
如果我们可以求出，通过兑换每种货币可以得到的最大值，那么问题便迎刃而解了。
因为要是可以得到的第S类货币最大值都不比初值大，资金肯定无法增加；否则，得到最大值的过程就是一种解法。
从问题本身来看，求最大值也是与其特性相符的。
因为：根据兑换的公式可以看出，兑换前的货币越多，那么兑换后得到的货币也会越多。就是说，原货币越多越好。
到了这里，我们发现求最大值和我们学过的求最短路很类似，构图用最短路算法做也显得水到渠成了。
具体做法是：
将N种货币看成N个结点，将每个兑换点转化为两条有向边。根据兑换公式，目前从A货币兑换到B货币的汇率和中转费用为RAB，CAB，那么由对应的A结点向B结点连一条有向边，从A点得到的B的可能最大值为：(A目前的最大值-CAB)×RAB。
注意，这里所求的是最大值，为了转化为最短路，我们可以在数字前面加上一个负号。
更简洁的方法是利用求最短路的方法，求最长路。 由于存在负权（求最长路和负权等价），所以在这里Dijkstra算法不适用了，我们可以用Bellman-Ford算法或者SPFA算法做，这里用Bellman-Ford就够了。
需要指出一点，无论是求负权最短路还是求最长路，可能遇到的一个问题是：存在环，从而导致货币最大值不存在（因为可以沿环使最大值不断增大）。
解决的办法其实很简单，我们只需要设立一个停止条件就行了。
如果当前没有点的最优值可以更新，又或者第S个点的最优值已经优于初始值，就可以退出循环了。
在细节上还有两点要注意。一是两点间的边可能不止一条，所以存图不能用邻接矩阵（从效率的角度也不提倡用），而应该用邻接表；二是涉及比较实数的大小，判断A 至此，本题解决。 小结： 想到求最大值是个人思维能力的体现；本题能够用求最大值解，却取决于题目本身的性质；采用最短路算法求最大值，由最短路模型的适用范围决定；对于细节的处理，则要靠以往的解题经验和平时的积累。 有时候，已经知道了应该用最短路做，但是选择不同的实现方式，时空效率有较大的差别，编程复杂度也有所不同，我们应该选择在时空复杂度可以接受的情况下，编程复杂度尽可能低的方式。就是说，要找到时空复杂度和编程复杂度的平衡点，写出性价比高的程序。 3．2 例题2——双调路径2 题意简述： 2 Baltic Olympiad in Informatics 2002 第11页 2006年全国信息学冬令营讲座 如今的道路密度越来越大，收费也越来越多，因此选择最佳路径是很现实的问题。城市的道路是双向的，每条道路有固定的旅行时间以及需要支付的费用。路径由连续的道路组成。总时间是各条道路旅行时间的和，总费用是各条道路所支付费用的总和。同样的出发地和目的地，如果路径A比路径B所需时间少且费用低，那么我们说路径A比路径B好。对于某条路径，如果没有其他路径比它好，那么该路径被称为最优双调路径。这样的路径可能不止一条，或者说根本不存在。 给出城市交通网的描述信息，起始点和终点城市，求最优双条路径的条数。城市不超过100个，边数不超过300，每条边上的费用和时间都不超过100。 分析： 本题显然是一道求最短路径的题目，不过和一般的问题也有所不同。 这道题棘手的地方在于标号已经不是一维，而是二维，因此不再有全序关系，初看似乎不能用最短路模型做。我们可以采用拆点法（这招在网络流问题上也很有用，比如点流量有限制的问题），让d[i,c]表示从s到i费用为c时的最短时间。 现在已经可以运用最短路算法做了。 我们面前有两条路：一是用标号设定算法，Dijkstra；二是用标号修正算法，Bellman-Ford或SPFA。 算法一： 标号设定算法是根据拓扑顺序不断把临时标号变为永久标号的。 在这题中，其实，我们并不需要严格的拓扑顺序，而只需要一个让标号永久化的理由。拓扑顺序能保证标号的永久化，但是还有其他方式。在本题中，标号永久化的条件是：从其他永久标号得不到费用不大于c且时间不大于t的临时标号（这里利用了费用和时间的非负性），即：所有的“极小临时标号”都可以永久化。这样，一个附加的好处是一次把多个临时标号同时变成永久的。 假设时间上限为t，费用上限为c，城市数为n，边数为m，则每个点上的标号不超过O(nc)个，标号总数为O(n2c)个，每条边考虑O(nc)次。如果不同顶点在同一费用的临时标号用堆来维护，不同费用的堆又组成一个堆的话，那么建立（或更新）临时标号的时间为O(mnclognlogc)，总的时间复杂度为O(n2c+mnclognlogc)，本题的规模是完全可以承受的。实际上由于标号的次数往往远小于n2c，程序效率是相当理想的。 算法二： 我们考虑在本题中运用SPFA算法的话，情况会是怎样？ 在最坏情况下，费用最大值c为100 * 100=10000，那么每个点将被拆成10000个点，由于原图边数不超过300，所以我们构造的新图中边数不会超过3000000。 根据我们之前的讨论可以知道，SPFA算法的平均时间复杂度是O(E)的。但是最坏情况下，复杂度可以达到O(VE)，对于本题而言，V=106，E=3*106，总复杂度将达到O(3*1012)之巨！ 实际上，即使是用Bellman-Ford算法，O(3*1012)的情况也极少出现（要做出这种数据真的不容易），更何况是SPFA了。 所以算法的复杂度应该是O(kE)，其中的k将会比V小很多。 还有一个好消息是：刚才对于时间复杂度的估计是基于一般图的，而本题非常特别。首先，费用的最大值，上限10000是很难达到的，它要求经过所有点， 第12页 2006年全国信息学冬令营讲座 并且每条边都是最大的费用100，一般来说，实际上限会比10000小很多。还有，图的构造也很特别，因为它的边是由最多只有300条边的原图拆出来的，每个结点拆出的所有点之间是相互独立的。 辅助队列应该采用循环队列，这样空间就不会浪费了。 写出来的程序运行的实际效果非常好，每个数据的速度都比官方参考程序（算法一）快，有几个甚至比官方程序快3~4倍！完全通过这题简直是轻而易举。这和我们对时间复杂度在理论上的分析是一致的。 在空间上和算法一是同阶的，一样是O(E)。虽然算法一仅用到二叉堆，并不是特别复杂，但是因为要用两个堆，建立更新删除写起来还是有一定的工作量的。SPFA算法写起来极其简单，效率又高，而且适用范围广（可以处理含有负权的图），在很多情况下，是最短路问题上好的选择。 建模和选择合适的实现方式是最短路的两个基础问题。 仅仅满足于此是远远不够的。 下面给出两道相对复杂的题目。它们的模型比较隐蔽，要求把题目抽象化，得出些本质的东西。考察的知识面也比较广泛，综合性较强。这里给出笔者思考解答的过程，力求做到：思路清晰，证明严谨，程序简洁高效。希望能抛砖引玉，对读者有所启发。 3．3 例题3——Layout3 题意简述： 当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。即使说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。 一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数L。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述，再给出MD条关于两头奶牛间存有反感的描述。（1<=ML,MD<=10000，1<=L,D<=1000000） 你的工作是：如果不存在满足要求的方案，输出-1；如果1号奶牛和N号 奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，1号奶牛和N号奶牛间可能的最大距离。 分析： 如果当前问题比较复杂，我们应该学会“退一步”思考，由简单到复杂。 求最大值不知从何下手，我们先从容易的开始分析。 我们先研究，如果不要求输出1和N的最大距离，而只需一个可行的距离，应该如何操作。 我们用D[i]表示I号奶牛和1号奶牛间的距离。 因为在队伍中的顺序必须和编号相同，所以对于任意I号奶牛，1<=I 3 Usaco Month Contest December 2005 Gold 第13页 2006年全国信息学冬令营讲座 D[I+1] - D[I] >= 0 对于每个好感的描述(i，j，k)，假设i<=j，体现到距离上的要求就是： D[j] - D[I] <= k 对于每个反感的描述(i，j，k)，假设i<=j，体现到距离上的要求就是： D[j] - D[I] >= k 这时的模型有一个名称，叫作：差分约束系统。 为了方便起见，我们将每种不等式写成我们约定的形式： D[I] <= D[I+1] D[j] <= D[I] + k D[I] <= D[j] - k 看到这些不等式，你想到了什么？ 没错，在求顶点间地最短路问题中，我们有这样的不等式： 若顶点u到顶点v有边e=uv，且边权为w(e)，设d(u),d(v)为源点到顶点u和顶点v的最短路长， 则 d(v) <= d(u) + w(e) 这个不等式和前面的条件形式十分相似，这就启发我们用构图用最短路做。 具体步骤是： 作有向图G=(V,E)，V={ v1，v2，v3，?，vn}，E={e1，e2，e3，?}，对于相邻两点i和(i+1)，对应的顶点vi+1向vi引一条边，费用为0；对于每组好感描述(ai，bi，di)，我们假设有ai 于是问题变为在G中求v1到其它所有顶点的最短路。我们证明若G中无负权回路，则问题有解，即存在满足条件的数列，若G中有负权回路，则问题无解，即不存在满足条件的数列。 定理5 问题是否有解等价于图G是否没有负权回路。 证明：若G中无负权回路，我们可以求出v1其他顶点u的最短路长，设为d(u)。由于是最短路，因此对于任意边e?E，e=uv，有d(u)+w(e)>=d(v)，从而所有的约束条件都被满足，问题一定有解。若G中有负权回路，说明在任何时刻，G中至少有一个点v的最短路长可以更新，因此必须存在一条边e=uv，使得d(u)+w(e) 检测负权回路，可以用Bellman-Ford算法。 回到原问题。 先说说考试时我的做法。 将所有点的最短路估计值设为一个充分大的值，v1的最短路估计值设为0。然后运行一次Bellman-Ford。 如果图G中有负权回路，那么输出-1； 否则，如果标号为N的顶点的最短路估计仍为一个充分大的值，那么它和标号为1的顶点间的距离可以任意大，这时输出-2； 如果以上两种情况都不满足，那么输出标号为N的点的最短路径估计值。 什么是充分大呢？ 只需要比原图中最大的边权×顶点数还大就行了。 第14页 2006年全国信息学冬令营讲座 因为只要无圈，每个顶点最多只会被经过一次，所以肯定比这个值小，所以在该图中，我们可以把这个值看作是无穷大。 该方法可以通过竞赛的所有测试数据。 考试的时候，我没有去刻意证明这个方法的正确性，只是感觉它应该可行。 现在让我们从理论上证明它。 定理6 若运行Bellman-Ford后，标号为N的顶点的最短路估计值仍为充分大，那么N和1的距离可以任意大。 证明：从刚才的操作可以看出，到了这一步，已经把含有负权回路的情况排除掉了。在图G中，该充分大的值比可能得到的最大距离大，因此，它和任意大的值对于G的效果都是一样的（同样大于合法的最大距离）。由于充分大的值在G中满足约束，所以任意大的值亦满足约束，从而距离可以任意大。（证毕） 剩下还有一个问题。 定理7 若运行Bellman-Ford后，标号为N的顶点的最短路估计值比充分大小，那么它是N和1可能的最大距离。 证明：设D[i]是顶点i和1的最短路径估计值，d[i]是顶点i和1可能的最大距离。 我们首先证明，d[n]<=D[n]，运用反证法。 假如d[n]>D[n]，那么在Bellman-Ford运行之前，将赋予每个顶点i的充分大的值换成对应的d[i]。由于d本身满足所有约束条件，所以运行后，得出D'=d。由于充分大的值比所有d[i]都大，而求最短路运用的是逐步松弛操作，我们设立一个更大的初值不可能导致我们的终值反而更小。所以对于任意i，必定有D[i]>=D'[i]，即有D[n]>=d[n]，这与我们的假设矛盾。 然后我们证明，d[n]>=D[n]。 根据d[i]的定义，它是i和1的可能最大距离。由于D[i]是满足题目的所有约束的，所以D[i]是顶点i和1可能的距离。如果D[i]>d[i]，那么与d[i]的定义矛盾。 综合上述，有D[i]=d[i]。从而D[n]是n和1可能的最大距离。（证毕） 运行Bellman-Ford最坏情况下的复杂度是O((ML+MD)*N)=O(2*107)，可以在规定时间内出解。另外，实际运行的速度相当理想，大部分数据运行基本上不需要时间。 3．4 例题4——网络提速4 某学校的校园网由n(1<=n<=50)台计算机组成，计算机之间由网线相连，如图5。其中顶点代表计算机，边代表网线。正如你所见，不同网线的传输能力不尽相同，例如计算机1与计算机2之间传输信息需要34秒，而计算机2与计算机3之间的传输信息只要10秒。计算机1与计算机5之间传输信息需要44秒，途径为机1到机3到机5。 现学校购买了m(1<=m<=10)台加速设备，每台设备可作用于一条网线，使网线上传输信息用时减半。多台设备可用于同一条网线，其效果叠加，即用两台设备，用时为原来的1/4，用三台设备，用时为原来的1/8。如何合理使用这些设备，使计算机1到计算机n传输用时最少，这个问题急需解决。校方请你编程 4 经典问题 第15页