题解 BZOJ 2725 故乡的梦

这个题在bzoj上好像是个权限题,想做的可以去Vani的博客下载测试数据。
这里有题面。

简单叙述一下题意
给你一个n个点、m条边的带权无向图,S点和T点,询问Q次删一条给定的边的S-T最短路。

其中 1<=n,m,q<=200000

ps. 1.这个题网上好多解法都是错的。2.这个题数据范围很大。

先求S到每个点的距离ds[i]。如果ds[T]为inf的话,输出Q个无解好了。
然后再求每个点到T的距离dt[i]。(用堆优化的Dijkstra即可。)

建一张最短路径图Gs仅包含ds[v]==ds[u]+w[u,v]这样的有向边。
同理再建一张最短路径图Gt仅包含dt[v]==dt[u]+w[u,v]这样的有向边。

我们可以发现在这两张最短路径图上,有一些关键边,与桥边类似,从S-T的最短路必经这些边。
可以知道,如果删掉的不是这些关键边,那么答案不会变,只有删掉关键边答案才会变。

这些关键边如何求呢?网上有些题解写的是把最短路径图看成无向图的桥边。(这个是有明显反例的,随便一拍都是反例,但是有的代码就是能过题 - -|)
还有的是用对Tarjan求桥边的时候做了一些限制,但是我觉得正确性未知。

我用了一种比较保(qi)险(guai)的方法,求出的这些关键边。

首先假设每条边的容量都是1,像网络流一样做两次增广,注意不需完整的最大流,只需两次增广。
如果流量>=2,说明这个图里没有关键边,直接输出Q个ds[T]即可。

那么我们来看流量是1的时候,很显然关键边就是能成为最小割的边(流量只有1),我们用Tarjan对这个图求一次强连通分量,设id[i]表示i这个点所属的连通分量编号。如果一条边(u,v)满流且id[u]!=id[v]那么这条边就可以成为最小割的一条边,即为关键边。
如果把Gs中的关键边反向就是Gt中的关键边。

我们就得到了GsGt中的关键边,这些关键边应该从S到T排成一列,不妨编号为1,2,3…。

我们考虑删除一条关键边(u,v),如果另一条非最短路图上的边(x,y)跨越了(u,v)那么ds[x]+w[x,y]+dt[y]就可能成为答案,这些(x,y)取min即可。

现在需要判断那些(x,y)可以跨越(u,v),有用了一种稳(qi)妥(guai)的方法判断的,将Gs,Gt中的边都给一个权值,如果这条边是关键边,那么这条边边权为1,否则这条边边权为0,然后我们在Gs上求一个这个图的最短路记为Ds[i],同理Dt[i],注意这里不用Dijkstra或SPFA,因为边权都是0/1所以来一次0/1 bfs即可(双端队列)。

Ds[i]Dt[i]的意义比较明显,从S到i点最短路经过最少关键边的数量,和从i点到T点最短路经过最少关键边的数量。那么我们就可以判断一条边是否跨过了第num条关键边,即为Ds[x]<num&&Dt[y]<sum-num (sum为关键边总数)。

但是每次枚举所以的边是不可能的,我们可以用离线的思想,预处理出每条关键边的答案。先预处理出Ds[i]值相等的点,可以存进一个vector。然后我们从左向右扫描这些关键边,从左向右扫描时,右端合法状态(Dt[y])是单调递减的,所以可以维护一个小根堆,代表现在可行的决策,堆中的关键字为ds[x]+w[x,y]+dt[y],那么堆顶就是一个最优方案。具体的讲,现在准备算第num条关键边,先把堆顶中Dt[y]>=sum-num的边删去,然后添加vector中Ds[i]==num的所有点的所有出边入堆,然后记录堆顶答案,算下一个num。

然后读入询问判一下是哪条边,输出答案即可。

程序写了不到6k。程序中变量名称对应题解中变量名称。

代码很丑。

https://gist.github.com/zrt/406a99ed44432c589179

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框