社区讨论
一点额外的理解
P5960【模板】差分约束参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @lobva1hc
- 此快照首次捕获于
- 2023/10/30 03:31 2 年前
- 此快照最后确认于
- 2023/11/04 08:33 2 年前
原式到三角形不等式的变形
如果变形为dis[i]<=dis[j]+d[j][i]的形式，求最短路，相当于对所有点的值加以多个上界约束 ；因而求出的解应当是最大的
如果变形为dis[i]>=dis[j]+d[j][i]的形式,求最长路，相当于对所有点的值加以下界约束，因而求出的解应当是最小的
那是不是说每个值的值域都能算出来？
回复
共 5 条回复，欢迎继续交流。
正在加载回复...