lkMiles

退役oier

差分约束

对差分约束系统的一点理解

一般的差分约束系统可以写成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了.....蠢哭了

评论
热度(1)
©lkMiles
Powered by LOFTER