V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
razrlele
V2EX  ›  问与答

关于网上的一段 POJ1860 代码松弛操作的疑问

  •  
  •   razrlele · 2014-08-18 15:33:16 +08:00 · 2158 次点击
    这是一个创建于 3751 天前的主题,其中的信息可能已经有所发展或是发生改变。
    http://blog.csdn.net/lyhvoyage/article/details/19281013

    这篇博文的Bellman-Ford 算法代码里面的松弛操作的一部分:

    for(int i = 1; i <= n - 1; i++)
    {
    bool flag = false;
    for(int j = 0; j < C; j++)
    {
    int a = p[j].a, b = p[j].b;
    double r = p[j].rate, c = p[j].cost;
    if(dis[b] < (dis[a] - c) * r)
    {
    dis[b] = (dis[a] - c) * r;
    flag = true;
    }

    }
    if(!flag)
    break;
    这里为什么加一个flag变量呢?
    我把flag去掉了一样可以AC, 并且时间也是0ms, 不是很理解作者在这里加flag的意图.

    对于Bellman-Ford算法还是不怎么理解, 希望有人帮忙解惑一下.
    4 条回复    2014-08-18 17:57:14 +08:00
    theJian
        1
    theJian  
       2014-08-18 16:04:18 +08:00   ❤️ 1
    bellman-ford是通过不断进行“松弛”操作得到最短路的,flag记录的是 是否本轮有节点被松弛,如果没有节点能再“松弛”,最短路也就得出了,可以跳出循环。
    GtDzx
        2
    GtDzx  
       2014-08-18 17:10:38 +08:00
    这里也有做POJ的小伙伴
    razrlele
        3
    razrlele  
    OP
       2014-08-18 17:28:33 +08:00
    @GtDzx 弱菜啊弱菜啊,多多指教啊
    wisatbff
        4
    wisatbff  
       2014-08-18 17:57:14 +08:00
    这种技巧叫剪枝。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1184 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 18:01 · PVG 02:01 · LAX 10:01 · JFK 13:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.