利用可持久化可并堆优化实现K短路

本来A*就可以搞定的题,为了怕以后卡复杂度,找了个这么个方法

现阶段水平不够就不补充算法分析部分了

对于图G,建立一个以终点t为起点的最短路径构成的最短路径树
(就是反着跑一遍最短路,然后对于一个不为终点的点v,v到终点t的最短路径上(任选一条)v的后继结点为v的父亲,就形成了一棵树)
然后对于所有点,定义其不在最短路径树上的出边的f值为:f[e] = l[e] + dis[e.tail] - dis[e.head] ,就是走这条边,走到t需要多绕的距离
那么我们只要找到第k小的这种边的序列就得到解了
那么我们维护按权值一个从小到大的优先队列,每次从队头取出一个序列q,设q的最后一条边e的head为u,tail为v
我们可以选择在序列的末尾加上v到t的所有路径上非树边的最小的得到一个新的序列q1
或者选择u到t的所有路径上所有非树边中e的后继(没用过的边中最小的)替换e得到q2,将q1,q2都塞进优先队列,重复k次,
可是怎么才能尽快知道一个节点v到t的所有路径上的非树边最小的一个呢?
打个可持久化的可并堆就没问题了,每个点合并他到根的路径上所有非树出边,然后对于找e的后继替换e的操作,直接找e的两个孩子就行了

本题难度爆表,低级图论和高级数据结构的大综合

直接上代码了,以后学的多了再回过头来看方法

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<queue>
  5 using namespace std;
  6 const int maxn=8005;  //为啥开这么大???
  7 const int maxm=100005;
  8 const int INF=0x7fffffff;
  9 int n,m,cnt,cntf,st,ed,k,tot,tp;
 10 bool vi[maxn];
 11 int g[maxn],gf[maxn],dis[maxn],_next[maxn],root[maxn],sta[maxn];
 12 struct Edge
 13 {
 14     int u,v,w,f,next;
 15     bool vis,flag;
 16 }e[maxm];
 17 struct Edgef
 18 {
 19     int t,w,next;
 20 }ef[maxm];
 21
 22 void addedge(int x,int y,int z)
 23 {
 24     cnt++;
 25     e[cnt].u=x;e[cnt].v=y;e[cnt].w=z;
 26     e[cnt].next=g[x];g[x]=cnt;
 27     e[cnt].vis=0;
 28 }
 29 void addedgef(int x,int y,int z)
 30 {
 31     cntf++;
 32     ef[cntf].t=y;ef[cntf].w=z;
 33     ef[cntf].next=gf[x];gf[x]=cntf;
 34 }
 35
 36 struct Node
 37 {
 38     int lc,rc,dis,c,y;
 39 }tr[maxn*100];
 40 int newnode(int c,int y)
 41 {
 42     tot++;
 43     tr[tot].lc=tr[tot].rc=0;
 44     tr[tot].dis=0;
 45     tr[tot].c=c;
 46     tr[tot].y=y;
 47     return tot;
 48 }
 49 int merge(int x,int y)
 50 {
 51     //cout<<x<<" "<<y<<endl;
 52     if(x==0||y==0) return x|y;
 53     if(tr[x].c>tr[y].c) swap(x,y);
 54     int ret=++tot;
 55     tr[ret]=tr[x];
 56     int k=merge(tr[ret].rc,y);
 57     if(tr[tr[ret].lc].dis<=tr[k].dis) swap(tr[ret].lc,k);
 58     tr[ret].rc=k;
 59     tr[ret].dis=tr[tr[ret].lc].dis+1;
 60     return ret;
 61 }
 62 struct HeapNode
 63 {
 64     int x,d;
 65 };
 66 bool operator <(HeapNode x,HeapNode y)
 67 {
 68     return x.d>y.d;
 69 }
 70 priority_queue<HeapNode> q;
 71
 72 struct Graph
 73 {
 74     int u,x,d;
 75 };
 76 bool operator < (Graph x,Graph y)
 77 {
 78     return x.d>y.d;
 79 };
 80 priority_queue<Graph> Q;
 81 void getdis()
 82 {
 83     dis[ed]=0;
 84     HeapNode temp;
 85     temp.x=ed;temp.d=0;
 86     q.push(temp);
 87     while(!q.empty())
 88     {
 89         HeapNode x=q.top();q.pop();
 90         if(dis[x.x]<x.d) continue;
 91         for(int tmp=gf[x.x];tmp;tmp=ef[tmp].next)
 92         {
 93             int y=ef[tmp].t;vi[y]=1;
 94             if(dis[y]>x.d+ef[tmp].w)
 95             {
 96                 dis[y]=x.d+ef[tmp].w;
 97                 temp.x=y;temp.d=dis[y];
 98                 q.push(temp);
 99             }
100         }
101     }
102 }
103 void solve(int x)
104 {
105     if(x==ed)
106     {
107         for(int tmp=g[x];tmp;tmp=e[tmp].next)
108         {
109             int y=e[tmp].v;
110             if(e[tmp].flag==0) continue;
111             if(e[tmp].vis==0)
112             {
113                 root[x]=merge(root[x],newnode(e[tmp].f,e[tmp].v));
114             }
115         }
116         return;
117     }
118     for(int tmp=g[x];tmp;tmp=e[tmp].next)
119     {
120         int y=e[tmp].v;
121         if(e[tmp].flag==0) continue;
122         if(e[tmp].vis==0)
123             root[x]=merge(root[x],newnode(e[tmp].f,e[tmp].v));
124         else root[x]=merge(root[x],root[y]);
125     }
126 }
127 int main()
128 {
129     int u,v,w;
130     scanf("%d%d",&n,&m);
131     for(int i=1;i<=m;i++)
132     {
133         scanf("%d%d%d",&u,&v,&w);
134         addedge(u,v,w);
135         e[cnt].flag=1;
136         addedgef(v,u,w);
137     }
138     scanf("%d%d%d",&st,&ed,&k);
139     if(st==ed) k++;
140
141     for(int i=1;i<=n;i++)
142         dis[i]=INF,vi[i]=0;
143     getdis();
144
145     if(k==1)
146     {
147         if(vi[st]) printf("%d\n",dis[st]);
148         else printf("-1\n");
149         return 0;
150     }
151     for(int i=1;i<=cnt;i++)
152     {
153         e[i].f=e[i].w-dis[e[i].u]+dis[e[i].v];
154         if(dis[e[i].v]==INF) e[i].flag=0;
155     }
156     for(int i=1;i<=n;i++)
157     {
158         if(i==ed) continue;
159         for(int tmp=g[i];tmp;tmp=e[tmp].next)
160         {
161             v=e[tmp].v;
162             if(!e[tmp].flag) continue;
163             if(dis[i]==dis[v]+e[tmp].w)
164             {
165                 e[tmp].vis=1;
166                 _next[i]=v;
167                 break;
168             }
169         }
170     }
171     memset(root,0,sizeof(root));
172     tot=0;
173     for(int i=1;i<=n;i++)
174         if(!root[i])
175         {
176             if(dis[i]==INF) continue;
177             sta[tp=1]=i;
178             while(1)
179             {
180                 u=sta[tp];
181                 if(u==ed) break;
182                 if(!root[_next[u]]) sta[++tp]=_next[u];
183                 else break;
184             }
185             while(tp)
186             {
187                 solve(sta[tp]);
188                 tp--;
189             }
190         }
191     k-=2;
192     Graph ss;
193     ss.u=st;ss.d=tr[root[st]].c;ss.x=root[st];
194     Q.push(ss);
195     while(k--)
196     {
197         Graph tmp=Q.top();Q.pop();
198         if(tmp.u==0)
199         {
200             printf("-1\n");
201             return 0;
202         }
203         if(tr[tmp.x].lc)
204         {
205             Graph tmp1;
206             tmp1.u=tmp.u;
207             tmp1.d=-tr[tmp.x].c;
208             tmp1.x=merge(tr[tmp.x].lc,tr[tmp.x].rc);
209             tmp1.d+=tr[tmp1.x].c+tmp.d;
210             Q.push(tmp1);
211         }
212         Graph tmp2;
213         tmp2.u=tr[tmp.x].y;
214         tmp2.d=tmp.d+tr[root[tmp2.u]].c;
215         tmp2.x=root[tmp2.u];
216         Q.push(tmp2);
217     }
218     Graph ans=Q.top();
219     if(ans.u==0)
220     {
221         printf("-1\n");
222         return 0;
223     }
224     if(vi[st]) printf("%d\n",dis[st]+ans.d);
225     else printf("-1\n");
226     return 0;
227 }

200多行幸亏没出什么调不出来的错误,唉,菜啊

原文地址:https://www.cnblogs.com/aininot260/p/9456891.html

时间: 08-10

利用可持久化可并堆优化实现K短路的相关文章

循环队列+堆优化dijkstra最短路 BZOJ 4152: [AMPPZ2014]The Captain

循环队列基础知识 1.循环队列需要几个参数来确定 循环队列需要2个参数,front和rear 2.循环队列各个参数的含义 (1)队列初始化时,front和rear值都为零: (2)当队列不为空时,front指向队列的第一个元素,rear指向队列最后一个元素的下一个位置: (3)当队列为空时,front与rear的值相等,但不一定为零: 3.循环队列入队的伪算法 (1)把值存在rear所在的位置: (2)rear=(rear+1)%maxsize ,其中maxsize代表数组的长度: 4.循环队列

Bzoj 1975: [Sdoi2010]魔法猪学院 dijkstra,堆,A*,K短路

1975: [Sdoi2010]魔法猪学院 Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 1357  Solved: 446[Submit][Status][Discuss] Description iPig在假期来到了传说中的魔法猪学院,开始为期两个月的魔法猪训练.经过了一周理论知识和一周基本魔法的学习之后,iPig对猪世界的世界本原有了很多的了解:众所周知,世界是由元素构成的:元素与元素之间可以互相转换:能量守恒……. 能量守恒……iPig 今

hdu1245+dij,堆优化

有一片100*100的湖泊,中心坐标(0,0),即湖泊右上角的坐标是(50,50),湖泊中间有一片以(0,0)为圆心,15为直径的圆形陆地.现有一个人在陆地,湖泊中散布着一些点可以踩,这个人要利用这些点跳到岸上,求最短路径和最短路径下的最短步数. spfa莫名其妙的超时,dij+堆优化反而能过...可能spfa更适合有向图吧. 使用vector<vector<node> > g这种双重结构时,最好先g.resize(N)设置一下容量,否则直接插入会出错. 1 #include<

dij+堆优化

写这个dij+堆优化的原因是有些地方卡SPFA,只能搞这个: 香甜的奶油: 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cstdlib> 6 #include<ctime> 7 #include<vector> 8 #include<algorithm> 9 #include&

[转]浅谈dijkstra堆优化

众所周知的,dijkstra是图论算法中求单源最短路的一种简单求法.可能有人会说SPFA比dijkstra要实用,而且可以用于求存在负边权的情况,但是dijkstra有着他的优点——其运行速度上优于SPFA. (PS.需要堆进行优化.) 我们先看一道经典(水)题: 平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间.其中的一些点之间有连线. 若有连线,则表示可从一个点到达另一个点,即两点之间有通路,通路的距离为两点之间的直线距离.现在的任务是找出从入点到出点之间的最短路

Dij的堆优化

#include<algorithm> #include<iostream> #include<cstdio> #include<cstring> #include<queue> #define M 100000 #define pa pair<int,int>//优先比较第一个元素 using namespace std; int d[M],n,m,cnt,head[M],next[M],u[M],dis[M],num,s,t; b

bzoj3040 最短路+配对堆优化

3040: 最短路(road) Time Limit: 60 Sec  Memory Limit: 200 MBSubmit: 1859  Solved: 564[Submit][Status][Discuss] Description N个点,M条边的有向图,求点1到点N的最短路(保证存在).1<=N<=1000000,1<=M<=10000000 Input 第一行两个整数N.M,表示点数和边数.第二行六个整数T.rxa.rxc.rya.ryc.rp. 前T条边采用如下方式生成

SPOJ 15. The Shortest Path 堆优化Dijsktra

You are given a list of cities. Each direct connection between two cities has its transportation cost (an integer bigger than 0). The goal is to find the paths of minimum cost between pairs of cities. Assume that the cost of each path (which is the s

BZOJ 3040 最短路(road) 堆优化Dijkstra

题目大意:最短路. 思路:最短路. 贴一份比较高效的堆优化Dij模板吧. CODE: #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define _MAX 1000010 #define MAX 10000010 using namespace std; #define min(a,b) ((a) < (b) ? a:b) long long

hdu 2544 单源最短路问题 dijkstra+堆优化模板

最短路 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 41168    Accepted Submission(s): 17992 Problem Description 在每年的校赛里.全部进入决赛的同学都会获得一件非常美丽的t-shirt.可是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的.所以如今他们想要寻