5660 - 提高:图论:差分约束 数形结合(模板)

通过次数

0

提交次数

1

时间限制 : 1 秒
内存限制 : 128 MB

给你一个不等式方程组,请你求出某个二个未知数差的最大值

输入

见样例,最后行是请你求二者差的最大值

输出

一个整数,如果无解输入N

样例

输入

x1 x2 <= 2
x2 x0 <= 7
x3 x0 <= 8
x2 x1 <= 3
x2 x1 <= 3
x3 x2 <= 2
x3 x0

输出

7

输入

x1 x2 <= 1
x2 x3 <= -5
x3 x1 <= 2
x4 x1 <= 3
x3 x5 <= 7
x4 x5

输出

N

提示

未知数最多到x9,注意题目里可能有重复的式子;
样例说明
x1- x2 <= 2
x2- x0 <= 7
x3- x0 <= 8
x2- x1 <= 3
x2- x1 <= 3
x3- x2 <= 2
求x3 -x0的最大值