我理解的差分约束。

    技术2024-10-20  28

    这几天没上线了,差分约束纠结了会儿。现在理解差不多了,基本有下面几个结论。

     

    如果求未知数的最大值,那么按小于等于建图后求最短路即可。(因为求最短路是由无穷向下约束而得到的,所以得到的一定是最大值)。

     

    如果求未知数的最小值,那么按小于等于建图后求最长路即可。

     

    注意所有数据的关系,不能漏掉关系,还有与附加源点的关系。

     

    如果是按大于等于建图:

     

    求最大值,建图后求最长路;

     

    求最小值,建图后求最短路。

     

    因为大于等于建图后,相当于未知数都*-1了,所以求出结果后需要*-1。

     

    最新回复(0)