差分约束系统转最短/最长路径：构造边与变形规则详解

差分约束系统题解1主要探讨了如何将差分约束问题转换为经典的最短路径问题，并利用图论方法来求解。首先，理解题目的关键在于对Dist数组的解释。在原最短路问题中，Dist数组记录了从起点到各个顶点的最短距离。在差分约束系统中，Dist[k]通常代表前k个数的和，可以用Dist[x]-Dist[k-1]来表示从第k个元素到第x个元素的距离，即sigma(k,k+1,……,x)。 问题中的限制条件，例如Dist[Bi]<=Dist[Ai]+K，表明可能存在从Ai到Bi的单向边，边权为K，用于在图中构造。同样的，如果限制条件是Dist[Ci]<=Dist[Di]-K，就需要构造从Di到Ci的单向边，边权为-K。这样的转化使得原本的不等式约束可以通过图上的边权重形式表达。 对于不同的目标问题，处理策略有所不同： 1. 求最大值或最短路径：开始时，Dist数组设置为极大值（例如无穷大），每次更新根据不等式约束，逐步逼近最优解。由于最短路径的性质，每次更新都会尽可能减小Dist，因此最终得到的是最大值。 2. 求最小值或最长路径：Dist数组初始化为0，每一次更新都按照约束进行，负值部分反映了约束条件的累计减少。最长路径会在满足约束的前提下尽可能增大Dist，但三角比较规则保持不变，因为边权为负值，会自动减少。 3. 求解存在性：若存在负环，即形成一个自环的约束，如a[i]>(<)a[i]+k，这种情况下无法找到满足约束的解。这是因为负环意味着某个点的Dist值可以无限制地增加，违反了约束的逻辑。 针对POJ1201的基础问题，题目给出一系列区间[Ai,Bi]，要求在这些区间内至少包含Ci个点。解决此类问题时，需要将这些区间转换为图中的节点和边，确保每个区间至少被选择的点数满足约束条件。通过构建适当的图并应用合适的算法（如Dijkstra或SPFA），可以找出满足所有区间需求的最小点集。 差分约束系统题解1的核心在于理解Dist数组的定义，将其与最短路径问题相结合，并根据问题类型调整算法策略。在实际操作中，需要灵活运用图的构造和搜索技巧，以求解出满足约束条件的最优解。