• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ2983 – Is the Information Reliable

    ACM-POJ EXP 135阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    题目大意

    给出M个表达式,判断这些信息是否可靠。

    解题思路

    差分约束+Bellman-Ford(建议用优化的Bellman-Ford

    设dist[i]为超级源点到i点的距离,则

    建立<=的差分系统:

    由于P A B X 指“确定A到B的距离(边权)为X”

    从P A B X得到的差分系统为

    dist[A] – dist[B] >= X && dist[A] – dist[B] <= X

    等价于

    dist[B] <= dist[A] – X && dist[A] <= dist[B] + X

    则if(dist[B] > dist[A]-X)松弛:dist[B] = dist[A]-X

    由于 V A B指“只知道A到B的距离(边权)至少为1”

    从V A B得到的差分系统为

    dist[A] >= dist[B] +1

    等价于

    dist[B] <= dist[A] -1

    则if(dist[B] > dist[A] -1) 松弛:dist[B] = dist[A] -1


    注意

    (1) 建立<=的差分系统,就必须求最短路(Bellman-Ford算法)。

    而信息是否可靠,就是判断图中是否存在负权回路(也是利用 Bellman-Ford判断)

    (2) 由于最坏有10W组不等式,经实测用scanf输入比cin要节省1500ms

    (3) 经实测用优化Bellman-Ford算法比普通Bellman-Ford算法快2000ms


    方法一:差分约束+优化Bellman

    转载请注明:EXP 技术分享博客 » POJ2983 – Is the Information Reliable

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址