企业官网建设流程全解析

分析

差分约束是什么？

差分约束是用来对一组不等式求解的一种算法。

推理和证明

把不等式抽象成一个图，每一条边都是一个不等式。求出满足所有边关系的距离就是每一个点的解。
求最小值按最长路，最大值按最短路。

假设有一条路x1>=x2+c2>=x3+c3,按最长路算时x3最小，同理x1<=x2+c2<=x3+c3,最短路,x1最大

怎么实现?

1. 建图(源点0要连向所有边)
2. 求最短路或最长路

例题

1. AcWing 1169. 糖果