BZOJ 1731 [Usaco2005 dec]Layout 排队布局


题目链接: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] 即可

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1731 [Usaco2005 dec]Layout 排队布局


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,