模板集

lun_hao · 2024-11-21 11:30:32 · 个人记录

前言：

洛谷、博客园、CSDN 同步更新

博客园 可能食用更佳

Part 0 缺省源 & 卡常

0.1 火车头

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

0.2 宏定义

#define re register
#define il inline
#define ls u<<1
#define rs u<<1|1
#define lowbit(x) (x&-x)
#define PII pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define clr(x) memset(x,0,sizeof(x))
#define ll long long
#define ld long double
#define pi acos(-1.0)

0.3 快读快写

#define il inline
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
char buf[1<<20],*p1,*p2;
template <typename T>
il void read(T &x)
{
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    x*=f;
}
template <typename T>
il void write(T x)
{
    if(x<0) putchar('-'),x=~x+1;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
il char getc()
{
    char ch=getchar();
    while(ch=='\n'||ch=='\r'||ch==' ') ch=getchar();
    return ch;
}

Part 1 最短路

1.1 Floyd

B3647 【模板】Floyd

时间复杂度 \mathcal O(n^3)

int n,m,dis[N][N];
void Floyd()
{
    read(n),read(m);
    memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=n;i++) dis[i][i]=0;
    for(int i=1,u,v,w;i<=m;i++)
    {
        read(u),read(v),read(w);
        dis[u][v]=dis[v][u]=min(dis[u][v],w);
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i^j&&i^k&&j^k&&dis[i][k])
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

1.2 Dijkstra

1.2.1 无优化 Dijkstra

P3371 【模板】单源最短路径（弱化版）

时间复杂度 \mathcal O(n^2)

int n,m,s,dis[N];
bool vis[N];
struct Edge
{
    int v,w;
};
vector<Edge> g[N];
void Dijkstra(int s)
{
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[s]=0;
    for(int i=1;i<n;i++)
    {
        int mindis=INF,u;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&mindis>dis[j])
                mindis=dis[j],u=j;
        vis[u]=1;
        for(auto [v,w]:g[u])
            if(!vis[v]&&dis[v]>mindis+w)
                dis[v]=mindis+w;
    }
}

1.2.2 堆优化 Dijkstra

P4779 【模板】单源最短路径（标准版）

时间复杂度 \mathcal O((m+n)\log n)

int n,m,s,dis[N];
bool vis[N];
priority_queue<PII,vector<PII>,greater<PII>> q;
struct Edge
{
    int v,w;
};
vector<Edge> g[N];
void Dijkstra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,q.push(mp(0,s));
    while(!q.empty())
    {
        int u=q.top().se;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto [v,w]:g[u])
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v]) q.push(mp(dis[v],v));
            }
    }
}

1.3 Bellman_Ford

1.3.1 无优化 Bellman_Ford

时间复杂度 \mathcal O(nm)

int n,m,dis[N];
struct Edge
{
    int u,v,w;
};
vector<Edge> e;
bool Bellman_Ford(int s)
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    bool flag=false;
    for(int i=1;i<=n;i++)
    {
        flag=false;
        for(auto [u,v,w]:e)
        {
            if(dis[u]==INF) continue;
            if(dis[v]>dis[u]+w)
                dis[v]=dis[u]+w,flag=true;
        }
        if(!flag) break;
    }
    return flag;
}

1.3.2 队列优化 SPFA

P3385 【模板】负环

时间复杂度 \mathcal O(nm)

int n,m,dis[N],cnt[N];
bool vis[N];
struct Edge
{
    int v,w;
};
vector<Edge> g[N];
queue<int> q;
bool SPFA(int s)
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop(),vis[u]=0;
        for(auto [v,w]:g[u])
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n) return false;
                if(!vis[v]) q.push(v),vis[v]=1;
            }
    }
    return true;
}

Part 2 最小生成树

P3366 【模板】最小生成树

2.1 Kruskal

时间复杂度 \mathcal O(m \log m)

int n,m,fa[N];
struct Edge
{
    int u,v,w;
}e[M];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void Kruskal()
{
    int mst=0,tot=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(e+1,e+1+m,[](Edge a,Edge b){return a.w<b.w;});
    for(int i=1;i<=m;i++)
    {
        int x=find(e[i].u),y=find(e[i].v);
        if(x==y) continue;
        fa[x]=y,mst+=e[i].w;
        if(++tot==n-1) break;
    }
    printf("%d",mst);
}

2.2 Prim

2.2.1 无优化 Prim

时间复杂度 \mathcal O(n^2)

int n,m,dis[N];
bool vis[N];
struct Edge
{
    int v,w;
};
vector<Edge> e[M];
void Prim()
{
    int u=1,tot=1,mst=0;
    memset(dis,0x3f,sizeof(dis));
    while(tot<n)
    {
        for(auto [v,w]:g[u])
            if(!vis[v]&&dis[v]>w) dis[v]=w;
        int mindis=INF;
        ++tot,vis[u]=1;
        for(int i=1;i<=n;i++)
            if(!vis[i]&&mindis>dis[i])
                u=i,mindis=dis[i];
        mst+=mindis;
    }
    printf("%d",mst);
}

2.2.2 堆优化 Prim

时间复杂度 \mathcal O((m+n) \log n)

int n,m,s,dis[N];
bool vis[N];
priority_queue<PII,vector<PII>,greater<PII>> q;
struct Edge
{
    int v,w;
};
vector<Edge> g[N];
void Prim()
{
    int mst=0,tot=0;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0,q.push(mp(0,1));
    while(!q.empty()&&tot<n)
    {
        int u=q.top().se;
        if(vis[u]) continue;
        ++tot,mst+=q.top().fi;
        vis[u]=1,q.pop();
        for(auto [v,w]:g[u])
            if(dis[v]>w)
                dis[v]=w,q.push(mp(dis[v],v));
    }
    printf("%d",mst); 
}

Part 3 最近公共祖先 LCA

P3379 【模板】最近公共祖先（LCA）

Tips：下列复杂度记作“预处理-询问”，m 次询问

你说的对，但是笔者不会 Tarjan 求解 LCA，故以后再来补

3.1 dfs 序 + 倍增

时间复杂度 \mathcal O(n \log n) - O(m \log n)，在线算法

int n,m,f[N][21],dep[N];
vector<int> g[N];
void dfs(int u,int fa)
{
    f[u][0]=fa,dep[u]=dep[fa]+1;
    for(int i=1;i<=19;i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(auto v:g[u])
        if(v^fa) dfs(v,u);
}
int LCA(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=19;~i;i--)
        if(dep[u]-dep[v]>=(1<<i)) u=f[u][i];
    if(u==v) return u;
    for(int i=19;~i;i--)
        if(f[u][i]^f[v][i])
            u=f[u][i],v=f[v][i];
    return f[v][0];
}

3.2 dfs 序 + 树剖

时间复杂度 \mathcal O(n)-\mathcal O(m \log n)，在线算法

int n,m,fa[N],dep[N],siz[N],hs[N];
vector<int> g[N];
void dfs1(int u,int fath)
{
    fa[u]=fath,dep[u]=dep[fath]+1;
    siz[u]=1,hs[u]=-1;
    for(auto v:g[u])
    {
        if(v==fath) continue;
        dfs1(v,u),siz[u]+=siz[v];
        if(hs[u]==-1||siz[v]>siz[hs[u]]) hs[u]=v;
    }
}
int top[N];
void dfs2(int u,int t)
{
    top[u]=t;
    if(~hs[u]) dfs2(hs[u],t);
    for(auto v:g[u])
        if(v^fa[u]&&hs[u]^v) dfs2(v,v);
}
int LCA(int u,int v)
{
    while(top[u]^top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    return v;
}

3.3 dfs 序 + ST 表

时间复杂度 \mathcal O(n \log n)-O(m)，在线算法

int n,m,st[N][21],dfn[N],cnt;
vector<int> g[N];
int get(int x,int y)
{
    return dfn[x]<dfn[y]?x:y;
}
void dfs(int u,int fa)
{
    st[dfn[u]=++cnt][0]=fa;
    for(auto v:g[u])
        if(v^fa) dfs(v,u);
}
int LOG[N];
void st_init()
{
    LOG[0]=-1;
    for(int i=1;i<=n;i++) LOG[i]=LOG[i>>1]+1;
    int p=LOG[n];
    for(int k=1;k<=p;k++)
        for(int s=1;s+(1<<k)<=n+1;s++)
            st[s][k]=get(st[s][k-1],st[s+(1<<(k-1))][k-1]);
}
int LCA(int u,int v)
{
    if(u==v) return u;
    u=dfn[u],v=dfn[v];
    if(u>v) swap(u,v);
    int k=LOG[v-u];
    return get(st[u+1][k],st[v-(1<<k)+1][k]);
}