首页 > 代码库 > 常见模板(欧拉筛素数,最小生成树,快排,并查集,单源最短路)

常见模板(欧拉筛素数,最小生成树,快排,并查集,单源最短路)

欧拉筛素数:

#include<cstdio>#define maxn 10000000+10using namespace std;int n,prime[5000001],num_prime=0,m;bool if_prime[maxn];void euler(int limit){    for(int i=2;i<=limit;i++)    {        if(!if_prime[i]) prime[++num_prime]=i;        for(int j=1;prime[j]*i<=limit&&j<=num_prime;j++)        {            if_prime[i*prime[j]]=true;            if(i%prime[j]==0) break;        }    }}int main(){    if_prime[1]=true;    scanf("%d%d",&n,&m);    euler(n);    int cur_1;    for(int i=1;i<=m;i++)    {        scanf("%d",&cur_1);        if(!if_prime[cur_1]) printf("Yes\n");        else printf("No\n");    }    return 0;}

单源最短路:

#include<queue>#include<cstdio>#define INF 2147483647LLusing namespace std;struct node {    int to,dis,next;};struct node edge[500005];int n,m,num,head[10001],dis_1[10001];inline void edge_add(int from,int to,int dis){    num++;    edge[num].to=to;    edge[num].dis=dis;    edge[num].next=head[from];    head[from]=num;}void SPFA(int start){    queue<int>que;    bool if_in_spfa[10001];    for(int i=1;i<=n;i++) dis_1[i]=INF,if_in_spfa[i]=false;    dis_1[start]=0,if_in_spfa[start]=true;    que.push(start);    while(!que.empty())    {        int cur_1=que.front();        que.pop();        for(int i=head[cur_1];i;i=edge[i].next)        {            if(dis_1[cur_1]+edge[i].dis<dis_1[edge[i].to])            {                dis_1[edge[i].to]=edge[i].dis+dis_1[cur_1];                if(!if_in_spfa[edge[i].to])                {                    if_in_spfa[edge[i].to]=true;                    que.push(edge[i].to);                }            }        }        if_in_spfa[cur_1]=false;    }}int main(){    int s;    scanf("%d%d%d",&n,&m,&s);    int from,to,dis;    for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&from,&to,&dis);        edge_add(from,to,dis);    }    SPFA(s);    for(int i=1;i<=n;i++) printf("%d ",dis_1[i]);    return 0;}

最小生成树:

#include<cstdio>#include<algorithm>using namespace std;struct node {    int from,to,dis;};struct node edge[200001];int num_head,num_edge,f[5001],num_2=0;int find(int x){    if(f[x]==x) return x;    else return f[x]=find(f[x]);}inline void edge_add(int from,int to,int dis){    num_2++;    edge[num_2].to=to;    edge[num_2].dis=dis;    edge[num_2].from=from;}bool cmp(struct node a,struct node b){return a.dis<b.dis;}int main(){    scanf("%d%d",&num_head,&num_edge);    int from,to,dis;    for(int i=1;i<=num_edge;i++)    {        scanf("%d%d%d",&from,&to,&dis);        edge_add(from,to,dis);    }    for(int i=1;i<=num_head;i++) f[i]=i;    sort(edge+1,edge+num_edge+1,cmp);    int head_1=0,num_1=0,sum=0;    while(num_1<num_edge)    {        num_1++;        int x=find(edge[num_1].from),y=find(edge[num_1].to);        if(x!=y)        {            sum+=edge[num_1].dis;            head_1++;            f[x]=y;        }        if(head_1==num_head-1) break;    }    if(head_1==num_head-1) printf("%d\n",sum);    else printf("orz\n");    return 0;}

并查集:

#include<cstdio>using namespace std;int n,m,f[10001];int find(int x){    if(f[x]==x) return x;    else return f[x]=find(f[x]);}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++) f[i]=i;    int now_1,now_2,cur_1;    for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&cur_1,&now_1,&now_2);        now_1=find(now_1),now_2=find(now_2);        if(cur_1==1) f[now_1]=now_2;        else now_1==now_2?printf("Y\n"):printf("N\n");    }    return 0;}

快排:

#include<cstdio>using namespace std;int i[100001],n;void Qsort(int t1,int t2){    int x=t1,y=t2,m=i[(t1+t2)>>1],t;    do    {        while (i[x]<m)          x++;        while (i[y]>m)          y--;        if (x<=y)        {            t=i[x];            i[x]=i[y];            i[y]=t;            x++;            y--;        }    }    while (x<=y);    if (t1<y)      Qsort(t1,y);    if (x<t2)      Qsort(x,t2);}int main(){    scanf("%d",&n);    for(int a=1;a<=n;a++) scanf("%d",&i[a]);    Qsort(1,n);    for(int a=1;a<=n;a++) if(a==1) printf("%d",i[a]);                            else printf(" %d",i[a]);    printf("\n");    return 0;}

 

常见模板(欧拉筛素数,最小生成树,快排,并查集,单源最短路)