hdu 1534(差分约束+spfa求最长路)

时间:2023-03-08 16:50:35
hdu 1534(差分约束+spfa求最长路)

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

思路:设s[i]表示工作i的开始时间,v[i]表示需要工作的时间,则完成时间为s[i]+v[i].于是可以列出下列不等式:

FAS  a b :b开始之后a结束,s[a]+v[a]>=s[b];

FAF a b  :b结束之后a结束,s[a]+v[a]>=s[b]+v[b];

ASF a b  :b结束之后a开始,s[a]>=s[b]+v[b];

ASA a b  :b开始之后a开始,s[a]>=s[b];

从而建图求最长路即可,需要注意的是一开始dist[]初始化为-inf.

http://paste.ubuntu.com/5932685/