Leaf-Salix.github.io

my blog

View on GitHub

【学习笔记】最短路计数

前言

在补一些之前写了没A的题目的时候遇到了逛公园这题

然后这位大佬的题解又让我再次看到了我之前写过的

P1144最短路计数

和没写过的

P1608路径统计

我本以为P1608路径统计是一道和最短路计数一样的水题,但是在遇到一些问题,进行一些思考之后,我发现我对最短路算法spfa和dijkstra的应用更加熟悉了一点点

我个人认为这篇文章对像我一样以前只会简单码spfa和dijkstra的同学将会有所裨益QAQ

我的思考过程

本文将向您展现我对这两题的一个思考过程,如果您对这两题的写法不是很清楚,可以参考我的思考过程

如果有哪些部分有误,还请与私信联系QAQ但是我马上就退役了,联系肯定是假的qwq

P1144最短路计数这题我的写法是spfa

	for(int i=1;i<=n;i++) dist[i]=2000001;
    dist[1]=0;v[1]=1;ans[1]=1;
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=h[x];i;i=e[i].nxt)
        {
            int y=e[i].v;
            if(dist[y]>dist[x]+1)
            {
                dist[y]=dist[x]+1;
                ans[y]=ans[x];
                if(!v[y])
                {
                    v[y]=1;
                    q.push(y);
                }
            }
            else if(dist[y]==dist[x]+1)
            {
                ans[y]=(ans[y]+ans[x])%100003;
                if(!v[y])
                {
                    v[y]=1;
                    q.push(y);
                }
            }
        }
        v[x]=0;
    }

也就是在处理spfa的时候当能够松弛(dist[y]>dist[x]+1)时,直接将ans[y]覆盖为ans[x],而相等时将到x最短路条数累加到y

由于spfa是广搜(但是也有在差分约束里判负环写dfs的spfa更快的,在这里不讨论,您可以自行思考),这题给的无权图相当于边权为1,注意,此时如果把搜索的顺序编为树,那么树的深度即为距离

比如

对于上面这幅图跑上面的算法搜索顺序(或者说更新顺序)是

所以在搜索4连到的点的时候,4的ans已经固定不会再改了(思考一下为什么)

当您搜完4所连点(我习惯叫做“扩展4”)之后,什么情况会再搜到4?

就是队列中在4后面的某一个点x有连向4的边,但是这个点x的深度/距离一定会大于等于4的深度/距离(spfa是广搜啊QAQ),因此x在搜到4时不会更新4的ans,更没有能力将4再次加入队列

同时您也会发现,当dist[y]==dist[x]+1时,我们可以不考虑再把y加入队列的事(删掉也能过)

因为此时肯定是队列中在x前的,与x深度相同的某一点x’也连到了y,将dist[y]=dist[x’]+1,这时候已经把y加入了队列里面,并且一定是在把这些深度为dist[y]-1的点都搜完了,把其中能连到y的点的答案累加到y之后才会扩展y

可惜的是我之前并没有这样思考,只是以为这题很水

直到我用同样的写法想AP1608路径统计

我错了

而其中的关键就在于,路径统计这题是有边权的

为什么?为什么有边权就会有问题?请思考一下。。。

因为如果您写的是spfa,边权影响了您的更新顺序

测试点1就是一个很好的例子

5 5
1 2 1
2 3 1
3 4 1
1 4 3
4 5 1

您会发现如果您这样写

 while(!q.empty())
    {
        int x=q.front();q.pop();v[x]=0;
        for(int i=h[x];i;i=e[i].nxt)
        {
            int y=e[i].v;
            if(dis[y]==1ll*dis[x]+e[i].w)
            {
                ans[y]+=ans[x];
                if(!v[y])
                    q.push(y),v[y]=1;
            }
            if(dis[y]>1ll*dis[x]+e[i].w)
            {
                dis[y]=dis[x]+e[i].w;
                ans[y]=ans[x];
                if(!v[y])
                    q.push(y),v[y]=1;
            }
        }
    }

输出的答案为4 3

而这样写

 while(!q.empty())
    {
        int x=q.front();q.pop();v[x]=0;
        for(int i=h[x];i;i=e[i].nxt)
        {
            int y=e[i].v;
            if(dis[y]==1ll*dis[x]+e[i].w)
            {
                ans[y]+=ans[x];
                //if(!v[y])
                    //q.push(y),v[y]=1;
            }
            if(dis[y]>1ll*dis[x]+e[i].w)
            {
                dis[y]=dis[x]+e[i].w;
                ans[y]=ans[x];
                if(!v[y])
                    q.push(y),v[y]=1;
            }
        }
    }

输出答案为4 1

对于4 3,是因为流程是

扩展1:搜到2,4,dis[2]=1,ans[2]=1,dis[4]=3,ans[4]=1

扩展2:搜到3,dis[3]=2,ans[3]=ans[2]=1

扩展4:搜到5,dis[5]=4,ans[5]=1

扩展3:搜到4,ans[4]=1

扩展4:搜到5,ans[5]+=ans[4]=3

对于4 1,是因为流程是

扩展1:搜到2,4,dis[2]=1,ans[2]=1,dis[4]=3,ans[4]=1

扩展2:搜到3,dis[3]=2,ans[3]=ans[2]=1

扩展4:搜到5,dis[5]=4,ans[5]=1

扩展3:搜到4,ans[4]=1

您会发现对于搜到了一个dis[y]==dis[x]+e[i].w的点y,您选择把它重新加入队列可能会造成答案重复,不加则可能会造成答案缺失

欸这个和刚刚说好的不一样啊

不一样的是树的深度不一定就是距离

这也就是:可能有一个深度大于x的点z,在扩展完x后,再次更新x

的ans,而此时x加入队列则会重复计数,不加入则会少计数

造成这样的结果是因为有边权

那我们怎么处理?

您注意到可能造成重复计算的是:扩展完x后有z使得x的答案被更新,此时我们需要再次更新x,但是又不能把上次扩展x时传出的答案再传一次

于是您可以选择:在上次扩展完x后把ans[x]清零

这样就能把这个问题解决了(但是不要像我这个傻逼一样把n点的答案也清零了)

while(!q.empty())
    {
        int x=q.front();q.pop();v[x]=0;
        for(int y=1;y<=n;y++)
        {
            if(g[x][y]==g[0][0]) continue;
            if(dis[y]==1ll*dis[x]+g[x][y])
            {
                ans[y]+=ans[x];
                if(!v[y])
                    q.push(y),v[y]=1;
            }
            if(dis[y]>1ll*dis[x]+g[x][y])
            {
                dis[y]=dis[x]+g[x][y];
                ans[y]=ans[x];
                if(!v[y])
                    q.push(y),v[y]=1;
            }
        }
        if(x!=n) ans[x]=0; 
    }

看似我们已经把这个问题解决了

但是我们再次思考一下,对于有权的图,我们难道不能做到在扩展x时保证x的ans不会再更新了吗?我们是学过这样的写法的!

在您翻阅题解之后会发现

为什么用dijkstra的根本没有考虑答案重复统计或者少统计的情况,就是因为dijkstra的贪心扩展过程保证了在扩展x时,x的ans不会再更新

好的,所以我们如果对dijsktra的理解度较高就可以想到用它来避免这个问题,而且根据spfa这种对一个点可能会重复搜几遍这种易被卡的性质,用dijkstra还是比较好

(说句题外话,我其实很希望有哪位大佬像写这题dijsktra可以避开spfa的问题一样,出一道题目卡一下dijsktra,当然除了负权边卡;不然我所知道的spfa的意义好像就只有跑负权图,找负权环了。。)

看似我们已经把这个问题解决了

但是我们还可以再瞄一眼边的范围

1~10?

反正我心动了

我们可以先用邻接矩阵存边,然后再用邻接表再建一次边,第二次建边时把x->y长度为c的边建成x->(cnt+1)->(cnt+2)->(cnt+c-1)->y并且每条边长度为1,然后就可以和P1144最短路计数一样的写法了

这里是写逛公园的一个hack题解

本人太菜QAQ,如果有错误请指出哦QAQ


2019.4.28