dijkstra与他的优化！！！
2024-08-29 11:24:51
@
SPFA已死，有事烧纸
其实我本人也是一个SPFA的忠诚用户，至少我的最少费用最大流都是用SPFA打的。但是，就在最近，发生了一个天大的丑闻！一个大佬竟将SPFA卡死！！！还有千千万万的SPFA站起来！！！
不过SPFA其实还是可以用来拿一定的分数，比如一些很神奇的优化。
这时，我们的\(dijkstra\)便一下子火了！
而且\(dijkstra\)也可以加优化，最快可以到达\(O(nlogn+m)\)，吊打SPFA？
Dijkstra
注：Dijkstra不能处理负边的情况。
首先，我们有四个点，1号点的点权为0，那么我们就用他更新其他的点。
那么现在在白色点里面，4号点是最小的，我们继续用4号点更新。
继续：
那么我们就可以得到一段代码。
bool bk[21000];
int d[21000];
d[0]=inf;
for(int i=1;i<n;i++)
{
int id=0;
for(int i=1;i<=n;i++)
{
if(!bk[i] && d[i]<d[id])id=i;
}//找最小
bk[id]=true;
for(int k=last[id];k;k=a[k].next)
{
int c=a[k].c;//边权
if(d[a[k].y/*边的另外一个终点*/]>d[id]+c)d[a[k].y]=d[id]+c;
}
}
当然，这种做法也是显而易见的正确了，在无负边的情况下当前距离最短的没被选过的点肯定不能被其他没被选过的点更新，实则就是加了贪心思想。
但是因为裸写的复杂度为\(O(n^{2}+m)\)，在找最小值方面较慢，所以也不行，需要用数据结构优化。
配对堆
引言
这里的配对堆不是pb_ds里面的！！！！！！！！！！！！！！！！！！！！
在无尽地堆海世界里面，有个叫斐波纳契堆的玩意，修改插入\(O(1)\)，弹出堆顶\(O(logn)\)，而二项堆则较为鸡肋，而这两个常数都大的一匹（代码也长）！！！
而二叉堆、优先队列（STL，开O2的话配对堆的时间和他差不了多少）、zkw线段树（不是堆，但这个常数真的小，配对堆跟他比还是慢一点），但是由于修改为\(O(logn)\)，导致时间复杂度变为\(O(n+mlogn)\)（优先队列的一般写法是\(O(n+logm)\)，因为不支持修改），但是常数小。
有没有综合一点的一个数据结构呢？
这是，配对堆便闪闪发光了，因为代码简洁和具备斐波纳契堆一样的复杂度，以及常数较小，被世人所赞叹，不过，还是存在许多不确定性的，毕竟没有完美的事物。
讲解
配对堆实质上是一棵树，用边目录进行连接
由于这个写的是排序，所以就比较简单，但是在优化Dij时因为要修改，为防止内存大和速度快，改了一些内容，当然，等你学会了排序后，这个差不多就会了。
下面讲
合并
两个堆的堆头，哪个小哪个为根，另外一个认他为父亲，就这么粗暴！！！
inline int merge(int x,int y){v[x]>v[y]?(x^=y^=x^=y):0;inz(x,y);return x;}
修改
就是我与父亲断绝关系，然后我修改我自己的值，将我与我的子树与root合并。
按我的理解是\(O(1)\)，而且对后面\(pop\)的影响也只是\(1\)或\(2\)次的影响，不知道为什么官方说是\(O(logn)\)，当然，此篇文章将按\(O(1)\)来算。
当然，这样只能改小，不能改大，改大的话可以断绝关系后pop一下然后再合并回来，\(O(logn)\)的时间。
void change(int id,LL x){v[id]=x;fa[id]=0;root=(root==id?id:merge(root,id));/*这条边就浪费了*/}//改变边权，这题不用
当然，边就浪费了，在后面会有一个回收的版本，但是慢一点，内存会小。
弹出堆顶pop
这么随便的一个数据结构为什么复杂度这么优秀，全看核心操作，pop()，将堆顶的所有儿子按一定顺序合并起来，然后弹出堆顶，而合并的顺序也是有讲究的，不是一个接一个，而是两两合并，这样每个点的儿子最多只有\(logn\)个，而配对堆时间复杂度最优秀的时候则是一条链的时候，排序都排序好了！
给个图好理解：
不是树，是合并的过程。
这个时候也许我们的儿子合并代码会这样写：
//vip为list中点的数量，list为儿子
int p=vip/2;
while(vip>1)
{
for(int i=1;i<=p;i++)list[i]=merge(list[i],list[i+p]);
(vip&1)?list[++p]=list[vip]:1;vip=p;p=vip/2;
}
但是大佬强就强在了这里（可以点击）：
int p=1;
while(p<vip)list[++vip]=merge(list[p],list[p+1]),p+=2;
简单，明了！！！！
那么给出pop完整的代码：
int list[M],vip;
inline void pop()
{
vip=0;
for(int k=las[root];k;k=e[k].next)
{
zjj.save(k)/*回收边的编号*/,(fa[e[k].y]==root?(be[list[++vip]=e[k].y]=fa[e[k].y]=0):0);
}
int p=1;
while(p<vip)
{
list[++vip]=merge(list[p],list[p+1]),p+=2;
}
las[root]=0;root=list[vip];
}
代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define N 110000
using namespace std;
typedef long long LL;
class dui
{
public:
struct neicun
{
int a[N],ts,len;
neicun(){ts=0;len=0;}
int get(){return ts?a[ts--]:++len;}
void save(int id){a[++ts]=id;}//存边
}zjj;//内存池
int root,fa[N]/*父亲*/;
LL v[N];//权值
struct node
{
int y,next;
}a[N];int len,last[N];
void ins(int x,int y){int now=zjj.get();a[now].y=y;a[now].next=last[x];last[x]=now;fa[y]=x;}//建边
int merge(int x,int y){v[x]>v[y]?(x^=y^=x^=y):0;ins(x,y);return x;}//合并
void push(int id,LL x){v[id]=x;root=(root?merge(root,id):id);}//推入堆中
void change(int id,LL x){v[id]=x;fa[id]=0;root=(root==id?id:merge(root,id));/*这条边就浪费了*/}//改变边权，这题不用
LL top(){return v[root];}
int list[210000],vip;
void pop()//踢出堆顶
{
vip=0;
for(int k=last[root];k;k=a[k].next)zjj.save(k),(fa[a[k].y]==root?fa[list[++vip]=a[k].y]=0:0);
int p=1;
while(p<vip)list[++vip]=merge(list[p],list[p+1]),p+=2;
last[root]=0;root=list[vip];
}
}zs;
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
LL x;scanf("%lld",&x);
zs.push(i,x);
}
for(int i=1;i<n;i++)
{
printf("%lld ",zs.top());
zs.pop();
}
printf("%lld\n",zs.top());
return 0;
}
结合！
1
那么，这道题目看着很简单，其实很恶心，因为如果你堆里面的边目录开到10000000，内存就炸裂，所以必须要将change的边回收，同时，一开始不要建所有的点，都是一些比较重要的细节。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define N 1000002
#define NN 2000002
#define M 10000002
using namespace std;
typedef long long LL;
//堆
bool type[N];
struct neicun
{
int qaq[N],ts,len;
neicun(){ts=0;len=0;}
int get(){return ts?qaq[ts--]:++len;}
void save(int id){qaq[++ts]=id;}
}zjj;//内存
int root;
LL v[N];
struct node
{
int x,y,next,step;//双向链表
}e[N];int las[N],be[N]/*自己连向父亲的那条边*/,fa[N];
inline void inz(int x,int y){int now=zjj.get();e[now].x=x;e[now].y=y;e[now].next=las[x];e[now].step=0;e[las[x]].step=now;las[x]=be[y]=now;fa[y]=x;}
inline int merge(int x,int y){v[x]>v[y]?(x^=y^=x^=y):0;inz(x,y);return x;}
inline void push(int id,LL x){v[id]=x;root=(root?merge(root,id):id);}
inline void put(int id){e[e[id].next].step=e[id].step;e[e[id].step].next=e[id].next;}//删点
inline void change(int id,LL x)
{
if(!type[id])
{
type[id]=true;
push(id,x);
return ;
}//一开始不要提前建所有的点
v[id]=x;
if(be[id]){put(be[id]);be[id]==las[fa[id]]?las[fa[id]]=e[be[id]].next:0;zjj.save(be[id]);fa[id]=be[id]=0;}
root=(root==id?id:merge(root,id));
}
inline int top(){return root;}
int list[NN],vip;
inline void pop()
{
vip=0;
for(int k=las[root];k;k=e[k].next)
{
zjj.save(k),(fa[e[k].y]==root?(be[list[++vip]=e[k].y]=fa[e[k].y]=0):0);
}
int p=1;
while(p<vip)
{
list[++vip]=merge(list[p],list[p+1]),p+=2;
}
las[root]=0;root=list[vip];
}
//
struct bian
{
int y,next,c;
}a[M];int len,last[N];//边目录
inline void ins(int x,int y,int c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
int o1;LL o2,o3,o4,o5,o6;scanf("%d%lld%lld%lld%lld%lld",&o1,&o2,&o3,&o4,&o5,&o6);
LL x=0,y=0;//建边
for(int i=1;i<=o1;i++)
{
x=(x*o2+o3)%o6;y=(y*o4+o5)%o6;
int a=int(x%(LL)n+1),b=int(y%LL(n)+1);
if(a>b)a^=b^=a^=b;
ins(a,b,1e8-100*a);
}//
for(int i=m-o1;i>=1;i--)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);
}
for(int i=1;i<=n;i++)v[i]=LL(99999999999999999);
change(1,0);
for(int i=1;i<n;i++)
{
int id=top();pop();
for(int k=last[id];k;k=a[k].next)
{
LL c=a[k].c;
if(v[a[k].y]>v[id]+c)change(a[k].y,v[id]+c);
}
}
printf("%lld\n",v[n]);
return 0;
}
虽然速度慢了点。
同时，这道题数据很水。
LL x=0,y=0;//建边
for(int i=1;i<=o1;i++)
{
x=(x*o2+o3)%o6;y=(y*o4+o5)%o6;
int a=int(x%(LL)n+1),b=int(y%LL(n)+1);
if(a>b)a^=b^=a^=b;
ins(a,b,1e8-100*a);
}
这一段建边可以不用，也可以A，同时你的速度也会快几十秒！！！
QAQ。
2
这道题目就很简单了吗！
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define N 100005
#define M 200005
using namespace std;
typedef long long LL;
bool type[N];
struct neicun
{
int qaq[N],ts,len;
neicun(){ts=0;len=0;}
int get(){return ts?qaq[ts--]:++len;}
void save(int id){qaq[++ts]=id;}
}zjj;
int root;
LL v[N];
struct node
{
int x,y,next,step;
}e[N];int las[N],be[N],fa[N];
inline void inz(int x,int y){int now=zjj.get();e[now].x=x;e[now].y=y;e[now].next=las[x];e[now].step=0;e[las[x]].step=now;las[x]=be[y]=now;fa[y]=x;}
inline int merge(int x,int y){v[x]>v[y]?(x^=y^=x^=y):0;inz(x,y);return x;}
inline void push(int id,LL x){v[id]=x;root=(root?merge(root,id):id);}
inline void put(int id){e[e[id].next].step=e[id].step;e[e[id].step].next=e[id].next;}
inline void change(int id,LL x)
{
if(!type[id])
{
type[id]=true;
push(id,x);
return ;
}
v[id]=x;
if(be[id]){put(be[id]);be[id]==las[fa[id]]?las[fa[id]]=e[be[id]].next:0;zjj.save(be[id]);fa[id]=be[id]=0;}
root=(root==id?id:merge(root,id));
}
inline int top(){return root;}
int list[M],vip;
inline void pop()
{
vip=0;
for(int k=las[root];k;k=e[k].next)
{
zjj.save(k),(fa[e[k].y]==root?(be[list[++vip]=e[k].y]=fa[e[k].y]=0):0);
}
int p=1;
while(p<vip)
{
list[++vip]=merge(list[p],list[p+1]),p+=2;
}
las[root]=0;root=list[vip];
}
struct bian
{
int y,next;
LL c;
}a[M];int len,last[N];
inline void ins(int x,int y,LL c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
int n,m,st;
LL d[N];
int main()
{
scanf("%d%d%d",&n,&m,&st);
for(int i=1;i<=m;i++)
{
int x,y;LL c;scanf("%d%d%lld",&x,&y,&c);
ins(x,y,c);
}
for(int i=1;i<=n;i++)d[i]=LL(99999999999999999);
d[st]=0;change(st,0);
for(int i=1;i<n;i++)
{
int id=top();
pop();
for(int k=last[id];k;k=a[k].next)
{
if(d[a[k].y]>d[id]+a[k].c)
{
d[a[k].y]=d[id]+a[k].c;
change(a[k].y,d[a[k].y]);
}
}
}
for(int i=1;i<n;i++)printf("%lld ",d[i]);
printf("%lld\n",d[n]);
return 0;
}
最新文章
- WPF中的动画——（三）时间线（TimeLine）
- html/css基础篇——link和@inport详解以及脚本执行顺序探讨
- MVC concept
- XE2编译出来的DLL的DLLMain的退出地方用到了halt0
- 一步步学习ASP.NET MVC3 (2)——入门程序
- Linux企业级项目实践之网络爬虫（7）——DNS解析
- Filter学习
- java的string.split()分割特殊字符时注意点
- iOS动画特效
- linux2.6.37内核接两个硬盘导致读写效率变低的问题
- Docker公共&本地镜像仓库（七）--技术流ken
- Polly 重试策略
- 调用 LoadLibraryEx 失败，在 ISAPI 筛选器 "C:\Windows\Microsoft.NET\Framework\v4.0.30319\\aspnet_filter.dll" 上
- 单机器搭建 zk 集群
- 深圳scala-meetup-20180902（3）- Using heterogeneous Monads in for-comprehension with Monad Transformer
- 启动设置mongodb
- WebMisSharp,WebMisCentral,企业框架正则表达式规则共享专版
- Promise 学习
- nodejs备忘总结(一) -- node和express安装与配置，新建简单项目（附安装配置过程中遇到问题的解决方法）
- vasa构架