本文使用 $LaTex$ 语法。若出现渲染失败或错误,请刷新页面并耐心等待刷新完成。

前言:明天就是退役赛CSP2021-S第二轮了,在此积攒RP。

$unsigned\ long\ long\ RP=2^{64}-1$,$RP++ $!

pb_ds平板电视

顾名思义就是一种电视

是一种被€€£允许在NOI系列考试中使用的奇技淫巧卡常技巧。

在部分OJ,如臭名昭著的洛谷上,可能会出现被反向优化的情况。不必担心其高效性。

2021.11.10 Update 本人已经冒着生命危险,在CSP上使用并证明了此用法的确高效。

这里主要说明一些 pb_ds 的优先队列的问题。

  • 用一道经典的题目为例。

【问题描述】

用二叉堆优化的 $Dijkstra$ 求一个有向图的最短路。

【输入格式】

第一行四个整数 $n,\ m,\ S,\ T$ 表示点数,边数,起点,终点;

接下来 $m$ 行每行三个整数 $a,\ b,\ v$ 表示有一条边 $a$ 到 $b$,边权是$v$。

【输出格式】

一个整数,表示最短路长度。

题目里说的很清楚了:二叉堆优化的 $Dijkstra$。干就完了!

光速打码。

#include<bits/stdc++.h>
using namespace std;

#ifndef ght
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
#endif

template<typename T>inline void read(T&ret) {
    ret=0;T f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    ret*=f;
}
template <typename T,typename... Args> inline void read(T& t, Args&... args){
    read(t);read(args...);
}
#define N 1000001

int n,m,s,t;
int dist[N],cnt,nxt[N],edge[N],to[N],head[N];
bool vis[N];
priority_queue<pair<int,int> >q;
void add(int u,int v,int w){
    edge[++cnt]=w;
    to[cnt]= v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    return ;
}

void dij(){
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;
    q.push(make_pair(0,s));
    while(q.size()){
        int x=q.top().second;q.pop();
        if(vis[x])continue ;
        vis[x]=1;
        for(int i=head[x];i;i=nxt[i]){
            int y=to[i],z=edge[i];
            if(dist[y]>dist[x]+z){
                dist[y]=dist[x]+z;
                q.push(make_pair(-dist[y],y));
            }
        }
    }
}
int a,b,v; 
signed main(){
    ios::sync_with_stdio(0);
    read(n,m,s,t);  
    for(int i=1;i<=m;i++){
        read(a,b,v);
        add(a,b,v);
    }
    dij();
    cout<<dist[t]<<'\n';
    return 0;
}

然后就A了。

但是。

但是!!

臭名昭著的STL库的函数效率,每次的priority_queue操作都达到了 $\Theta(logN)$。而这有时候是不能接受的。

这时候便可以搬上主角了:

一台电视

pb_ds 库全称 Policy-Based Data Structures

pb_ds 库封装了很多数据结构,比如哈希(Hash)表,平衡二叉树,字典树(Trie 树),堆(优先队列)等。就像 vectorsetmap 一样,其组件均符合 STL 的相关接口规范。部分(如优先队列)包含 STL 内对应组件的所有功能,但比 STL 功能更多。

pb_ds 只在使用 libstdc++ 为标准库的编译器下可以用。

————以上信息摘自OI Wiki

我们知道,priority_queue任何操作都达到了 $\Theta(logN)$(上文已经说过)。但是使用此优化,可以使常用的push(以及一些不常用的东西)的复杂度降至$\Theta(1)$,在频繁输入时效率拔高显著。

它为什么快?不知道而且关我屁事

  • 首先,一定要先引入 pb_ds 头文件。它并不在万能头文件bits/stdc++.h中,因为万能头不万能它是扩展库。
#include <ext/pb_ds/assoc.container.hpp>
  • 随后是优先队列所需的头文件。
#include <ext/pb_ds/priority_queue.hpp>
  • 声明方式:
__gnu_pbds::priority_queue<...>q;//括号内为适当的声明,与普通的优先队列基本没有区别。
//普通的:<int,vector<int>>
//这个:<int>

甚至更短了。

完了?完了。

  • 上最终代码(顺便放上Spfa写法):
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;

#ifndef ght
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
#endif

template<typename T>inline void read(T &ret){
    ret=0;T f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
    ret*=f;
}
template <typename T,typename... Args> inline void read(T&t,Args&... args){
    read(t);read(args...);
}

#define N 1000001
int n,m,s,t,a,b,v;
int hed[N],nxt[N],to[N],edge[N],cnt;
void add(int u,int v,int k){
    edge[++cnt]=k;
    to[cnt]=v;
    nxt[cnt]=hed[u];
    hed[u]=cnt;
    return ;
}

int dist[N];
bool vis[N];

void dij(){
    __gnu_pbds::priority_queue<pair<int,int>>q;
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(vis[x])continue ;
        for(int i=hed[x];i;i=nxt[i]){
            int y=to[i],z=edge[i];
            if(dist[y]>dist[x]+z){
                dist[y]=dist[x]+z;
                q.push(make_pair(-dist[y],y));
            }
        }
    }
}

void spfa(){    //关于Spfa:他死了
    queue<int>q;
    memset(dist,0x3f,sizeof dist);
    q.push(s);
    vis[s]=1;
    dist[s]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=hed[u];i;i=nxt[i]){
            int v=to[i];
            if(dist[v]>dist[u]+edge[i]){
                dist[v]=dist[u]+edge[i];
                if(!vis[v])q.push(v),vis[v]=1;
            }
        }
    }
}

signed main(){ios::sync_with_stdio(0);
    read(n,m,s,t);
    for(int i=1;i<=m;i++){
        read(a,b,v);
        add(a,b,v);
    }
    spfa();
    cout<<dist[t]<<endl;
    return 0;
}

  • 可以看出来 $Dijkstra$ 部分几乎没有区别。这就是 pb_ds 的一大优点。不需要像__int128之类的卡常那么麻烦

  • 当然,pb_ds 还有非常之多的功能。不过就先记到这里吧。


The Only Thing That's Changed is EVERYTHING .