poj3169 layout差分约束的证明。。。

在Acm论文中看到的，一起学习一下，至少解决了我不少疑问。
3．3 例题3——Layout
题意简述：
当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。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<N，在距离上应该满足：
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<bi，否则ai和bi交换，则顶点vai向vbi引一条边，费用为di；对于每组反感描述(ai，bi，di)，我们假设有ai<bi，否则ai和bi交换，则顶点vbi向vai引一条边，费用为-di。
于是问题变为在G中求v1到其它所有顶点的最短路。我们证明若G中无负权回路，则问题有解，即存在满足条件的数列，若G中有负权回路，则问题无解，即不存在满足条件的数列。
定理5 问题是否有解等价于图G是否没有负权回路。
证明：若G中无负权回路，我们可以求出v1其他顶点u的最短路长，设为d(u)。由于是最短路，因此对于任意边eE，e=uv，有d(u)+w(e)>=d(v)，从而所有的约束条件都被满足，问题一定有解。若G中有负权回路，说明在任何时刻，G中至少有一个点v的最短路长可以更新，因此必须存在一条边e=uv，使得d(u)+w(e)<d(v)。所以无论何时，都会有某个约束条件不被满足，问题无解。（证毕）
检测负权回路，可以用Bellman-Ford算法。
回到原问题。
先说说考试时我的做法。
将所有点的最短路估计值设为一个充分大的值，v1的最短路估计值设为0。然后运行一次Bellman-Ford。
如果图G中有负权回路，那么输出-1；
否则，如果标号为N的顶点的最短路估计仍为一个充分大的值，那么它和标号为1的顶点间的距离可以任意大，这时输出-2；
如果以上两种情况都不满足，那么输出标号为N的点的最短路径估计值。
什么是充分大呢？
只需要比原图中最大的边权×顶点数还大就行了。
因为只要无圈，每个顶点最多只会被经过一次，所以肯定比这个值小，所以在该图中，我们可以把这个值看作是无穷大。
该方法可以通过竞赛的所有测试数据。
考试的时候，我没有去刻意证明这个方法的正确性，只是感觉它应该可行。
现在让我们从理论上证明它。
定理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]的定义矛盾。www.zzzyk.com
综合上述，有D[i]=d[i]。从而D[n]是n和1可能的最大距离。（证毕）
运行Bellman-Ford最坏情况下的复杂度是O((ML+MD)*N)=O(2*107)，可以在规定时间内出解。另外，实际运行的速度相当理想，大部分数据运行基本上不需要时间。

补充：软件开发 , C++ ,

上一个：排序算法详解（一）
下一个：Poj 2605 SETI (数学_高斯消元)