差分约束
对差分约束系统的一点理解
一般的差分约束系统可以写成x(i)<=x(j)+d的形式,这样的话如果我们要求x(j)-x(i)的最小值的话,那么就说明不能更小了,一些条件使得它最小只能到这里了,所以条件应该是>=,也就是说我们建边的时候注意是按照最长路的思路来建,如果是求x(j)-x(i)的最大值的话就说明一些条件使得它不能再大了,那么条件就是<=,建边就是按照最短路的思路来建.
大概是在口胡,ovo但是tangyuhao说如果遇到了,构造一个不合法的情况,如果是负环就是最短路,正环就是最长路似乎也是挺有道理的...
然后就是一套差分系统并不一定只有一个解,就是说每个x(i)有可能是能够求出[l[x],r[x]]的...
好晕....
贴上两道练习题:
BZOJ2330 糖果
BZOJ1731 排队
因为要反应到底是最短路还是最长路所以就会想很久QAQ果然智商不够.
//这种带判定的最好写dfs版的spfa,smg阿今天spfa被卡加边顺序了...果然脸黑.
//丢脸的发现自己现在不会写spfa了.....蠢哭了