这几天没上线了,差分约束纠结了会儿。现在理解差不多了,基本有下面几个结论。
如果求未知数的最大值,那么按小于等于建图后求最短路即可。(因为求最短路是由无穷向下约束而得到的,所以得到的一定是最大值)。
如果求未知数的最小值,那么按小于等于建图后求最长路即可。
注意所有数据的关系,不能漏掉关系,还有与附加源点的关系。
如果是按大于等于建图:
求最大值,建图后求最长路;
求最小值,建图后求最短路。
因为大于等于建图后,相当于未知数都*-1了,所以求出结果后需要*-1。