再探第k短路
发布日期:2022-02-07 06:39:36 浏览次数:14 分类:技术文章

本文共 3912 字,大约阅读时间需要 13 分钟。

其实这是一个很古老的姿势啦…

只不过今天跟同学讨论A*算法求k短路的时候,同学不信A*算法能被卡掉.
于是我翻了翻课件找出了一种 n 元环的特殊情况,卡掉了A*算法.
A*算法是只有到达终点的时候才能统计答案,这导致可能拓展很多个状态才能得到一个用来更新答案的有效状态.
例如一个
n
元环,当我们到达终点之后,可能还要拓展 n 次才能得到下一个状态.于是若求
k
短路时间复杂度就为 O(nk) .于是就容易被卡掉.
我们考虑换一种方式来定义一条从起点 s 到终点
t
的路径.
构建出以 t 为终点的最短路树,
t
是这棵树的根,对于剩下的所有点 x 都有一个父亲点
pax
表示 x
t
的最短路上 x 的后继.若存在多个后继,则随意选择一个.
现在我们有了一个唯一的树结构.
考虑一条路径,这是一个边序列,其中有树边和非树边,我们将其中的树边去掉,仅考虑非树边.
dist(x,y)
表示从 x
y
的最短路径长度,则走一条非树边 xy 会使答案增加 len(x,y)(dist(x,t)dist(y,t)) .
(珍爱生命,远离微软输入法!)
我们可以预先处理出从 s
t
的最短路径长度,于是对于所有路径,求出其中非树边的代价和,再加上 s,t 最短路长度就是我们想要的答案.
于是我们将问题转化为第 k 小的合法非树边序列的代价和.
首先我们需要证明一个事情,就是一个合法的非树边序列唯一对应一条从
s
t 的路径.
让我们先来看看一个非树边序列是合法的条件:
考虑在序列中相邻的两条边
e,f
,那么一定满足条件 head(f) tail(e) 到根的路径上.
这是因为在两条路径之间只能走树边,而树边必定是指向根节点的,所以深度必定减少,因此上述结论是成立的.
由这个结论,我们显然可以发现一个非树边序列唯一对应一条从 s
t
的路径.
我们可以由这个性质对于非树边序列进行拓展:
假如某个状态的最后一条非树边是 e ,我们就把所有起点在
tail(e)
到根的路径上的非树边附加在 e 的后面当做一个新的状态拓展下去.
同时依然利用优先队列维护即可.
然而这样是极其爆炸的.对于一个状态,我们最多可以拓展出
O(m)
个状态,也就是说总的状态数为 O(km) ,无法接受.
我们不妨考虑对于所有的点维护一个堆存下所有起点在这个点到根路径上的非树边,这样当我们从一个非树边序列向下拓展时,只有以下两种情况:
在结尾加上一条非树边:只需要取最后一条边的终点的堆中的最小边即可.
将最后一条边替换为另一条边:只需要将序列中的最后一条边替换为堆中这条边的儿子即可.
用可持久化的堆来维护这些边即可.
时间复杂度 O((n+m)logn+mlogm+klogk) .
这样就可以了.是很稳定的算法.
下面是我的代码.

#include
#include
#include
#include
#include
#include
using namespace std;#define mp make_pair#define pb push_back#define inf 0x3f3f3f3f#define N 10010int n,m,K;typedef long long ll;typedef pair
pii;struct SegmentTree{ pii s[32768]; int M; inline void init(int _siz){ for(M=1;M<(_siz+2);M<<=1); for(int i=0;i<(M<<1);++i) s[i]=mp(inf,0); } inline void modify(int x,int y){ for(s[x+M]=mp(y,x),(x+=M)>>=1;x;x>>=1) s[x]=min(s[x<<1],s[x<<1^1]); } inline int getid(){ return s[1].second; }}Seg;struct Graph{ static const int V=N; static const int E=100010; int head[V],next[E],end[E],len[E],ind; inline void reset(){ ind=0; memset(head,0,sizeof head); } inline void addedge(int a,int b,int c){ int q=++ind; end[q]=b; next[q]=head[a]; head[a]=q; len[q++]=c; }}g,_g,tree;int d[N];inline void dijkstra(int s,Graph&g){ memset(d,0x3f,sizeof d); Seg.init(n); d[s]=0; Seg.modify(s,0); for(int i=1;i<=n;++i){ int x=Seg.getid(); for(int j=g.head[x];j;j=g.next[j]){ if(d[g.end[j]]>d[x]+g.len[j]){ d[g.end[j]]=d[x]+g.len[j]; Seg.modify(g.end[j],d[g.end[j]]); } } Seg.modify(x,inf); }}int pa[N];struct Node{ Node*l,*r; int v,tail,dist; Node():dist(0){}}mempool[1000010],*P=mempool,Tnull,*null=&Tnull;inline Node*newnode(int _v,int _tail){ P->l=P->r=null; P->v=_v; P->tail=_tail; P->dist=1; return P++;}inline void copy(Node*&p,Node*q){ if(q==null) p=null; else *p=*q;}inline Node*merge(Node*p,Node*q){ Node*s=P++; if(p==null||q==null){ copy(s,p==null?q:p); return s; } if(p->v>q->v) swap(p,q); copy(s,p); s->r=merge(p->r,q); if(s->l->dist
r->dist) swap(s->l,s->r); s->dist=s->r->dist+1; return s;}Node*root[N];struct State{ ll ldist; Node*ledge; State():ldist(0ll),ledge(null){} State(ll _ldist,Node* _ledge):ldist(_ldist),ledge(_ledge){} bool operator<(const State&B)const{ return ldist>B.ldist; }};priority_queue
Q;bool treeedge[100010];int main(){ cin>>n>>m>>K; int i,j,a,b,c; g.reset(); _g.reset(); for(i=1;i<=m;++i){ scanf("%d%d%d",&a,&b,&c); g.addedge(a,b,c); _g.addedge(b,a,c); } dijkstra(n,_g); for(i=1;i
q; q.push(n); Node*p; root[0]=null; while(!q.empty()){ i=q.front(); q.pop(); root[i]=merge(null,root[pa[i]]); for(j=g.head[i];j;j=g.next[j]) if(!treeedge[j]){ p=newnode(g.len[j]-(d[i]-d[g.end[j]]),g.end[j]); root[i]=merge(root[i],p); } for(j=tree.head[i];j;j=tree.next[j]) q.push(tree.end[j]); } if(K==1) cout<
<
v,root[1])); State tmp; ll ldist; Node*ledge; for(int i=1;i<=K;++i){ tmp=Q.top(); Q.pop(); ldist=tmp.ldist; ledge=tmp.ledge; if(i==K){ cout<
<
tail]->v,root[ledge->tail])); if(ledge->l!=null) Q.push(State(ldist-ledge->v+ledge->l->v,ledge->l)); if(ledge->r!=null) Q.push(State(ldist-ledge->v+ledge->r->v,ledge->r)); } } return 0;}

就这样吧…

转载地址:https://blog.csdn.net/wyfcyx_forever/article/details/45875055 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:多线程和异步操作的异同
下一篇:可移植C/C++设计

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月21日 09时31分28秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

hdfs orc格式_处理 HDFS 上的过多小文件的问题? 2019-04-21
缺失magisk正常工作所需的文件_总结了十个工作表看上去很凌乱的原因 2019-04-21
matlab将二值图像与原图重叠_MATLAB--数字图像处理 图像直方图规定化 2019-04-21
ptp输出内容包含什么_免费小程序开发包含哪些内容,相对APP有什么优势 2019-04-21
python re sub 替换多个_Python随笔23:Python基础编程练习题11~12 2019-04-21
宠物龟 扫地机器人_帮着做家务,新品科沃斯T5扫地机器人比宠物还听话,比老公更好用... 2019-04-21
np 数组转为普通数组_一起学数据分析之NumPy(13)——用于数组的文件输入输出 2019-04-21
绿联网卡转接mac设置_使用徕卡、哈苏相机时,这些问题你遇到过吗?(二) 2019-04-21
dns改成什么网速快_这个DNS服务器不仅更快而且安全 2019-04-21
增大表名最大长度_让1人测量飞机40米长度,钢卷尺很难搞定,小米激光测距仪来帮你... 2019-04-21
5单个编译总会编译全部_速度与激情:Webpack5 &amp; 极速编译 2019-04-21
用etree解析xml_用 Python 抓取 bilibili 弹幕并分析! 2019-04-21
检查域名是否可以访问_医用检查手套是否可以重复使用? 2019-04-21
如何区分用户_通信中的多址技术:基站如何区分不同用户,时分与频分多址技术... 2019-04-21
div旋转 vue_Vue实现按钮旋转和移动位置的实例代码_蜡烛_前端开发者 2019-04-21
switchresx卸载_SwitchResX 2019-04-21
python游走代码_python实现BA网络选取节点(deepwalk选取下一个游走节点) 2019-04-21
java sublist_java中利用List的subList方法实现对List分页(简单易学) 2019-04-21
mac电脑循环次数多少算新_苹果电脑电池循环次数多少才正常? 2019-04-21
10000内的亲密数_RICKYOUNG圣诞内购会 | 把暖冬快乐送给你 2019-04-21