破烂默写本

· · 个人记录

背诵默写部分常用内容。

缺省源

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,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();}
    return x*f;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9){write(x/10);}
    putchar((x%10)+48);
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);

    return 0;
}

并查集（路径压缩）

int f[N],n;
inline void init(){
    for(int i=1;i<=n;i++)f[i]=i;
    return;
}
int find(int d){
    if(f[d]!=d)f[d]=find(f[d]);
    return f[d];
}
inline void uni(int x,int y){
    f[find(x)]=find(y);
    return;
}
inline bool check(int x,int y){
    return (find(x)==find(y));
}

链式前向星

int h[N],to[M],nxt[M],tot=-1;
inline void add(int u,int v){
    to[++tot]=v;
    nxt[tot]=h[u];
    h[u]=tot;
}//只建边，边之类的自己写
//只建单向边，无向边写两遍即可
//这个写法边的其实编号为0,判断是否遍历完写 ~i
//编号从1开始就写tot=0即可，判断是否遍历完写 i!=0
//编号从0还是需要先把整个h数组赋值为-1

SPFA（无负环）

void spfa(){
    while(!q.empty())q.pop();
    for(int i=1;i<=n;i++){dis[i]=inf;}
    dis[s]=0;inque[s]=1;q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(int i=h[u];~i;i=nxt[i]){
            int v=to[i];
            if(dis[v]>dis[u]+w[i]){
                dis[v]=dis[u]+w[i];
                if(inque[v]==0){
                    inque[v]=1;
                    q.push(v);
                }
            }
        }
    }
}

SPFA（判断负环）

int dis[N],inque[N],in[N];
queue<int>q;
bool spfa(){
    while(!q.empty())q.pop();
    for(int i=1;i<=n;i++){dis[i]=inf;in[i]=0;inque[i]=0;}
    dis[s]=0;inque[s]=1;in[s]=1;q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(int i=h[u];~i;i=nxt[i]){
            int v=to[i];
            if(dis[v]>dis[u]+w[i]){
                dis[v]=dis[u]+w[i];
                if(inque[v]==0){
                    inque[v]=1;
                    q.push(v);
                    ++in[v];
                    if(in[v]>n){
                        return true;
                    }
                }
            }
        }
    }
  return false;
}

堆优化——迪杰斯特拉

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+7,M=2e5+7,inf=1e9+7;
int n,m,s;
int h[N],to[M],nxt[M],w[M],tot=-1;
inline void add(int u,int v,int z){
    to[++tot]=v;
    nxt[tot]=h[u];
    w[tot]=z;
    h[u]=tot;
}
int dis[N],vis[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
//小根堆
void dij(){
    for(int i=1;i<=n;i++){
        dis[i]=inf;
    }
    pair<int,int>tmp;
    dis[s]=0;
    tmp.first=dis[s];
    tmp.second=s;
    q.push(tmp);
    while(!q.empty()){
        tmp=q.top();
        q.pop();
        int d=tmp.first;
        int u=tmp.second;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=h[u];~i;i=nxt[i]){
            int v=to[i];
            if(dis[v]>d+w[i]){      
                dis[v]=d+w[i];
                if(!vis[v]){
                    pair<int,int>tmmp;
                    tmmp.first=dis[v];
                    tmmp.second=v;
                    q.push(tmmp);
                }
            }
        }
    }
}
int main(){
    n=read();m=read();s=read();
    for(int i=1;i<=n;i++)h[i]=-1;// pay attention to it
    for(int i=1;i<=m;i++){
        int u,v,z;
        u=read();v=read();z=read();
        add(u,v,z);
    }
    dij();
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    return 0;
}

LCA(倍增的写法)

void dfs(int x,int f){
    dep[x]=dep[f]+1;
    fa[x][0]=f;
    for(int i=1;i<=18;i++){
        fa[x][i]=fa[fa[x][i-1]][i-1];
        if(fa[x][i]==0)break;
    }
    for(int i=h[x];~i;i=nxt[i]){
        if(to[i]!=f){
            dfs(to[i],x);
        }
    }
    return;
}
int lca(int a,int b){
    if(dep[a]<dep[b])swap(a,b);
    for(int i=18;i>=0;i--){
        if(dep[fa[a][i]]>=dep[b])a=fa[a][i];
    }
    if(a==b)return a;
    for(int i=18;i>=0;i--){
        if(fa[a][i]!=fa[b][i]){
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
//数字18的地方根据题目自行修改

最小生成树（克鲁斯卡尔）

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,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();}
    return x*f;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9){write(x/10);}
    putchar((x%10)+48);
}
const int N=2e5+7;
struct edge{
    int u,v,w;
}e[N];
bool cmp(edge x,edge y){
    if(x.w<y.w)return true;
    else return false;
}
int n,m,f[N],tot,ans;
int find(int x){
    if(x!=f[x])f[x]=find(f[x]);
    return f[x];
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        e[i].u=read();
        e[i].v=read();
        e[i].w=read();
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        int u=e[i].u;
        int v=e[i].v;
        int w=e[i].w;
        if(find(u)!=find(v)){
            ans+=w;
            f[find(u)]=find(v);
            ++tot;
        }
    }
    if(tot==n-1)write(ans);
    else cout<<"orz";
    return 0;
}