首页 > 代码库 > 常见模板（欧拉筛素数，最小生成树，快排，并查集，单源最短路）
常见模板（欧拉筛素数，最小生成树，快排，并查集，单源最短路）
欧拉筛素数：
#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;}
常见模板（欧拉筛素数，最小生成树，快排，并查集，单源最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。