5大模板（普及组）

【模板】最小生成树（Kruskal$Kruskal$）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n,m,i,j,u,v,total;
struct edge{
    int start,to;long long val;
}bian[2000005];
int f[100000];
long long ans;

int find(int x)
{
    if (f[x]==x) return x; else 
    {
        f[x]=find(f[x]);
        return f[x];
    }   
}

bool cmp(edge a,edge b)
{
    return a.val<b.val;
}

inline void kruskal()
{

    for(int i=1;i<=m;i++)
    {
        u=find(bian[i].start);
        v=find(bian[i].to);
        if(u==v) continue;
            ans+=bian[i].val;
            f[u]=v;
            total++;
            if(total==n-1) break;
    }
} 
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) f[i]=i;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&bian[i].start,&bian[i].to,&bian[i].val);
    }
    sort(bian+1,bian+m+1,cmp);
    kruskal();
    printf("%d",ans);
    return 0;
}

【模板】并查集

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int f[100000];
int i,j,n,m,z,x,y,u,v;
int find(int x)
{
    if (f[x]==x) return x; else 
    {
        f[x]=find(f[x]);
        return f[x];
    }   
}
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) f[i]=i;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&z,&x,&y);
        if(z==1)
        {
            u=find(x);
            v=find(y);
            if(u!=v) f[u]=v;
        }
        else
            if(find(f[x])!=find(f[y]))  printf("N\n");else printf("Y\n");
    }
}

【模板】单源最短路径（SPFA$SPFA$）

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
struct node{
    int to,val,next;
}edge[500000 + 100];
int stu[500000 + 100]; 
int tot=0,q[1000000],f,ans[10000+100],n,m,s,a,b,c;
bool vis[500000+100];
void add(int u,int v,int w){
    edge[++tot].to = v;
    edge[tot].val = w;
    edge[tot].next = stu[u];
    stu[u] = tot;
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    memset(stu,0,sizeof(stu));
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    memset(vis,0,sizeof(vis));
    memset(ans,0x3f,sizeof(ans));
    ans[s]=0;
    int i=0;
    int j=1;
    vis[s]=true;
    q[1]=s;
    while(i<=j)
    {
        i++;
        f=stu[q[i]];
        while(f!=0)
        {
            //ans[edge[f].to]=min(ans[edge[f].to],ans[q[i]]+edge[f].val);
            if(ans[edge[f].to]>ans[q[i]]+edge[f].val)
            {
                ans[edge[f].to]=ans[q[i]]+edge[f].val;
                if(vis[edge[f].to]==false)
                {
                    q[++j]=edge[f].to;
                    vis[edge[f].to]=true;
                }
            }
            f=edge[f].next;
        }
        vis[q[i]]=false;
    }
    for(int i=1;i<=n;i++)
    {
        if (ans[i]==1061109567) printf("2147483647 ");else printf("%d ",ans[i]);
    }
    return 0;
}

【模板】堆

#include<iostream>
#include<sstream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[1000005];
int i,j,n,total,x,y;
inline void push(int y)
{
    a[++total]=y;
    for(int i=total,j=i>>1;j;i=j,j=i>>1)
    {
        if(a[j]>a[i]) swap(a[i],a[j]);
    }
}
inline void pop()
{
    a[1]=a[total--];
    for(int i=1,j=i<<1;j<=total;i=j,j=i<<1)
    {
        if(j+1<=total&&a[j+1]<a[j]) j++;
        if(a[i]<a[j]) break; else swap(a[i],a[j]);
    }
}
int main()
{
    scanf("%d",&n);
    total=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(x==1)
        {
            scanf("%d",&y);
            push(y);
        }
        if(x==2) printf("%d\n",a[1]);
        if(x==3) pop();
    }
}

【模板】快速排序(pascal$pascal$)

var
        a:array[1..100000] of longint;
        n,i,j:longint;
procedure qsort(l,h:longint);
var
        i,j,t,m:longint;
begin
        i:=l; j:=h;
        m:=a[(i+j) div 2];
        repeat
                while a[i]<m do inc(i);
                while m<a[j] do dec(j);
                if i<=j then
                begin
                        t:=a[i]; a[i]:=a[j]; a[j]:=t;
                        inc(i); dec(j);
                end;
        until i>j;
        if i<h then qsort(i,h);
        if j>l then qsort(l,j);
end;
begin
        read(n);
        for i:=1 to n do
                read(a[i]);
        qsort(1,n);
        for i:=1 to n do
                write(a[i],' ');
end.

【模板】快速排序(c++$c++$)

#include<cstdio>
#include<iostream>
using namespace std;
int a[1000000],i,j,n,m;
void qp(int l,int r)
{
    int i=l,j=r,mid=a[(l+r)/2];
    do
    {
        while(a[i]<mid) i++;
        while(a[j]>mid)j--;
        if(i<=j)
        {
            a[0]=a[i];
            a[i]=a[j];
            a[j]=a[0];
            i++;j--;
        }
    }while(i<=j);
    if(l<j) qp(l,j);
    if(i<r) qp(i,r);
}
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    qp(1,n);
    for(i=1;i<=n;i++)printf("%d ",a[i]);
}