hdu 1531(差分约束)

时间:2024-10-16 17:36:08

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1531

差分约束的题之前也碰到过,刚好最近正在进行图论专题的训练,就拿来做一做。

①:对于差分不等式,a - b <= c ,建一条 b 到 a 的权值为 c 的边,求的是最短路,得到的是最大值
②:对于不等式 a - b >= c ,建一条 b 到 a 的权值为 c 的边,求的是最长路,得到的是最小值

③:存在负环的话是无解

④:求不出最短路(dist[ ]没有得到更新)的话是任意解

说明一下为什么存在负环就是无解?我们的目标是求不等式的解,而不等式的解正是超级源点到各点的最短距离,而如果存在负环的话,是无法求得最短距离的,从而也就无法求出不等式的解。

回到本题,我们可以设s[i] = a[1] + a[2] + …… + a[i],于是就有a[Si] + a[Si+1] + ... + a[Si+ni] = s[Si+ni] - s[Si-1],从而就有s[si+ni]-s[si-1]>ki或者s[si+ni]-s[si-1]<ki,对不等式做处理变为s[si-1]-s[si+ni]<=-(ki+1),s[si+ni]-s[si-1]<=ki-1。从而求最短路就行了。这里直接判负环就可以了。

http://paste.ubuntu.com/5932520/