关于visit

P3376 【模板】网络最大流

Seauy @ 2020-02-03 17:01:09

为什么一定要拓展了之后马上标记而不是走到一个地方就标记啊 qwq

正解:

for(msg now,rear;!Q.empty();Q.pop())
{
    now=Q.front();
    //printf("now at: %d minc: %d\n",now.loc,now.minc);
    for(int i=0;i<G[now.loc].size();i++)
        if(G[now.loc][i].Left>0)
        {
            rear.loc=G[now.loc][i].nxt;
            if(visit[rear.loc]) continue;
            rear.minc=min(now.minc,G[now.loc][i].Left);
            pre[rear.loc]=G[now.loc][i].oppo;
            if(rear.loc==t) return rear.minc;
            Q.push(rear);
            visit[rear.loc]=1;
        }
}

然而这么写 10TLE

for(msg now,rear;!Q.empty();Q.pop())
{
    now=Q.front();
    //printf("now at: %d minc: %d\n",now.loc,now.minc); 
    if(visit[now.loc]) continue;
    visit[now.loc]=1;
    for(int i=0;i<G[now.loc].size();i++)
        if(G[now.loc][i].Left>0)
        {
            rear.loc=G[now.loc][i].nxt;
            rear.minc=min(now.minc,G[now.loc][i].Left);
            pre[rear.loc]=G[now.loc][i].oppo;
            if(rear.loc==t) return rear.minc;
            Q.push(rear);
        }
}

[ 难道这就是我 BFS 经常爆炸的原因?qwq ]


by Seauy @ 2020-02-03 17:01:50

是因为没有标记,其他节点拓展时就会继续更改吗...


|