为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 268752
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

求解过程:

1、 问题条件转换

条件转换成下面一组不等式 x1 - x2 <= b1 x2 - x3 <= b2 x3 - x1 <= b3 ...................

2、 求解:

1) 要判断是否存在这样的x1, x2, x3……满足所有不等式,则以任意为源点,求出所有点的最短路(即可作为xi的值)。(因为边权可能为负,用Bellman-ford求最短路,如果存在负圈则无解);

2) 要求xn – x1的最大值,则初始化为极大,做x1xn的最短路;

3) 要求xn – x1的最小值,则初始化为极小,做x1xn的最短路

3、注意
不等式一定是小于等于或者大于等于。

posted on 2009-09-08 15:06 baby-fly 阅读(195) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理