2024NOIP模板代码复习专用文章

最短路

dijkstra题目

代码

#include<bits/stdc++.h>
#define ll long long
#define N 200001  // 最大的顶点数和边数
using namespace std;

// 初始化全局变量
int a[N],n,m,ver[N],nxt[N],head[N],w[N],tot,vis[N],u,maxx;

// 图的添加边函数
void add(int x,int y,int z){
        ver[++tot]=y;   // 边的另一个顶点
        nxt[tot]=head[x];  // 上一条以 x 为起点的边
        head[x]=tot;    // 以 x 为起点的最新的边
        w[tot]=z;       // 边的权值
}

int main(){
        cin>>n>>m;  // 输入顶点数和边数
        // 读入所有的边
        for(int i=1;i<=m;i++){
                int x,y,z;
                cin>>x>>y>>z;
                add(x,y,z);
                add(y,x,z);
        }
        // 初始化 a 数组为无穷大，表示点 i 到点 1 的最短路径
        memset(a,0x3f3f3f3f,sizeof a);
        a[1]=0;  // 点 1 到自己的最短路径为 0

        // Dijkstra算法主体
        for(int i=2;i<=n;i++){
                maxx=0x3f3f3f3f;
                u=0;
                // 找到未被访问的距离最小的顶点
                for(int j=1;j<=n;j++){
                        if(!vis[j]&&a[j]<maxx){
                                maxx=a[j];
                                u=j;
                        }
                }
                vis[u]=1;  // 标记该点为已访问
                // 更新通过 u 点到其他点的最短路径
                for(int j=head[u];j;j=nxt[j]){
                        a[ver[j]]=min(a[ver[j]],a[u]+w[j]);
                }
        }
        // 输出结果
        if(a[n]==0x3f3f3f3f){ // 如果从点 1 到点 n 无法到达
                cout<<"-1";
        }
        else{
                cout<<a[n]; // 输出最短路径
        }
        return 0;
}

并查集

题目

代码

#include<bits/stdc++.h>
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
const int N=1e4+5;
int n,m,f[N];
int Find(int x){
    if(x==f[x]){
        return x;
    }
    return f[x]=Find(f[x]);
}
void unionn(int x,int y){
    x=Find(x);
    y=Find(y);
    f[x]=y;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=1;i<=m;i++){
        int x,y,op;
        cin>>op>>x>>y;
        if(op==1){
            unionn(x,y);
        }
        else{
            if(Find(x)==Find(y)){
                cout<<"Y\n";
            }
            else {
                cout<<"N\n";
            }
        }
    }
    return 0;
}

kruskal最小生成树

题目

代码

#include<bits/stdc++.h>
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
const int N=2e5+2;
int n,m,f[N];
struct node{
    int s,f,q;
}a[N];
int Find(int x){
    if(x==f[x]){
        return x;
    }
    return f[x]=Find(f[x]);
}
bool cmp(node a,node b){
    return a.q<b.q;
}
int kruskal(){
    sort(a+1,a+1+m,cmp);
    int ans=0,tot=0;
    for(int i=1;i<=m;i++){
        int xx=Find(a[i].s);
        int yy=Find(a[i].f);
        if(xx==yy) continue;
        f[xx]=yy;
        ans+=a[i].q;
        tot++;
        if(tot==n-1){
            return ans;
        }
    }
    return -1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>a[i].s>>a[i].f>>a[i].q;
    }
    int cnt=kruskal();
    if(cnt==-1){
        cout<<"orz";
    }
    else{
        cout<<cnt;
    }
    return 0;
}

线性筛之埃氏筛

题目

代码

#include<bits/stdc++.h>
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
const int N=1005;
int n,q,vis[N],p[N],cnt;
int main(){
    cin>>n>>q;
    vis[1]=1;
    for(int i=2;i<=sqrt(n);i++){
        if(vis[i]==1){
            continue;
        }
        for(int j=i*i;j<=n;j+=i){
            vis[j]=1;
        }
    }
    for(int i=2;i<=n;i++){
        if(vis[i]==0){
            p[++cnt]=i;
        }
    }
    for(int i=1;i<=q;i++){
        int x;
        cin>>x;
        cout<<p[x]<<"\n";
    }
    return 0;
}