POJ – 2983 – Is the Information Reliable? (差分约束系统)

题目链接:POJ - 2983 题目大意: 有部分点之间知道具体相对位置, 有部分点仅知道一点在另一点的某边。 问是否存在这样的点集。 题目分析: 建图,差分约束系统。 注意的是,对于spfa(),要加入一个权为0的超级源点,使得图连通。 bellman-ford算法则不需要。 给出代码: #inc…

POJ – 1201 – Intervals (差分约束系统)

题目链接:POJ - 1201  题目大意:有一个序列,题目用n个整数组合 [ai,bi,ci]来描述它,[ai,bi,ci]表示在该序列中处于[ai,bi]这个区间的整数至少有ci个。如果存在这样的序列,请求出满足题目要求的最短的序列长度是多少。 题目分析: 利用差分约束转化成图的最短路…