已经通过,但是求教原理

回复帖子

@杜岱玮 2018-01-12 22:03 回复

书上说差分约束系统只能求出一类特殊线性规划问题的可行解,无法最大化目标函数。可这道题可以用差分约束求解并得到最优解,我也通过了,但对其原理却很不清楚,只是直觉上觉得可行。有没有人能给出一个严谨些的解释?

https://www.luogu.org/record/show?rid=5326561

我的答案,SPFA加二叉堆