关于取地址变量

P3376 【模板】网络最大流

g1ove @ 2024-08-21 09:13:04

下面是两份 dinic：

    for(int i=pre[x];i&&sum;i=e[i].next)
    {
        pre[x]=i;
        ......
    }

    for(int &i=pre[x];i&&sum;i=e[i].next)
    {
        ...
    }

下面的跑了 1s，上面的跑了 92ms

为什么下面的这么慢

by jason_sun @ 2024-08-21 09:25:18

下面的写法是错误的

by g1ove @ 2024-08-21 09:29:11

@jason_sun 蒟蒻不是很懂，dalao能解释解释吗

by jason_sun @ 2024-08-21 09:32:53

你去翻翻这题讨论区，经典错误了

by gavinliu266 @ 2024-08-21 10:01:34

@g1ove 下面的写法会跳过一条流量不满的边。

事实上只要在每一次增广之后判断流量 sum 如果小于 0 就 break 的话，下面的写法也就是对的。

by gavinliu266 @ 2024-08-21 10:04:40

就是这两种都是对的：

for(int i=pre[x];i&&sum;i=e[i].next)
{
    pre[x]=i;
    // 增广
}

for(int &i=pre[x];i;i=e[i].next)
{
    pre[x]=i;
    // 增广
    if(!sum) break;
}

by g1ove @ 2024-08-21 10:13:27

@gavinliu266 感谢回答，明白了

在一条可流的边跳过了，执行了跳到下一条边，使得增广次数大大增加复杂度就假了