BZOJ 1731 [Usaco2005 dec]Layout 排队布局

发布于 2017-06-16  92 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1731

题意:一些奶牛在数轴上,有些奶牛间有两两距离不能超过或者不能小于某值的限定,问 1 到 n 的最大距离...


差分约束系统裸题,首先最大距离转换为最短路模型... 记录约束关系 x,y 中,x<=y

对于限制 1,连接 x->y L

对于限制 2,连接 y->x -D

令 dis[1]=0, 不需要额外建立虚拟源点,若 1 不与 n 连通,则 n 没有限制,可以无穷大

若有负权环,则不存在一组合法解,否则输出 dis[n] 即可

 


一个非常弱的准退役OIER