CSP复习与模板

P3366 【模板】最小生成树

Kruskal 算法因为只与边相关，则适合求稀疏图的最小生成树。而 Prim 算法因为只与顶点有关，所以适合求稠密图的最小生成树。

Prim 是以更新过的节点的连边找最小值，Kruskal 是直接将边排序。两者其实都是运用贪心的思路。

Kruskal

Kruskal 的时间复杂度为 \(O(e\log e)\)，只和边有关系。

#include<cstdio>

#include<algorithm>

#define reg register

using namespace std;

const int N=5005,M=200005;

struct Edge{

    int u,v,w;

    bool operator<(const Edge x){

        return w<x.w;

    }

}e[M];

int fa[N],ans,n,m,tot;

int father(int x){

    return fa[x]==x?x:fa[x]=father(fa[x]);

}

int main(){

    scanf("%d%d",&n,&m);

    for(reg int i=1;i<=n;++i)fa[i]=i;

    for(reg int i=1;i<=m;++i)

        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

    sort(e+1,e+m+1);

    for(reg int i=1;i<=m;++i){

        int fx=father(e[i].u);

        int fy=father(e[i].v);

        if(fx==fy)continue;

        fa[fx]=fy;

        ans+=e[i].w;

        tot++;

        if(tot==n-1)break;

    }

    if(tot<n-1)printf("orz");

    else printf("%d",ans);

    return 0;

}

Prim 的时间复杂度为 \(O(n^2)\)，可近似认为只和点有关。

#include<cstdio>

#include<algorithm>

#define reg register

using namespace std;

const int N=5005,M=200005,INF=1000000000;

struct Edge{

    int u,v,w,next;

    Edge(int _u=0,int _v=0,int _w=0,int _next=0):

        u(_u),v(_v),w(_w),next(_next){}

}e[M<<1];

int n,m,ans,top,head[N];

inline void add(int u,int v,int w){

    e[++top]=Edge(u,v,w,head[u]);

    head[u]=top;

}

int dis[N]; bool vis[N];

int main(){

    scanf("%d%d",&n,&m);

    for(reg int i=1,u,v,w;i<=m;++i){

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w); add(v,u,w);

    }

    dis[1]=0;

    for(reg int i=2;i<=n;++i){

        dis[i]=INF;

    }

    for(reg int i=1;i<=n;++i){

        int u=-1,Min=INF;

        for(reg int j=1;j<=n;++j){

            if(!vis[j] && dis[j]<Min){

                u=j; Min=dis[j];

            }

        }

        if(u==-1){

            printf("orz");

            return 0;

        }

        vis[u]=true;

        ans+=dis[u];

        for(reg int x=head[u];x;x=e[x].next){

            int v=e[x].v;

            if(dis[v]>e[x].w)dis[v]=e[x].w;

        }

    }

    printf("%d",ans);

    return 0;

}

最短路

P4779 【模板】单源最短路径（标准版）

堆优化 dijkstra

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cstring>

#define reg register

using namespace std;

const int MN=100005;

int n,m,s,top;

struct Edge{

    int u,v,w,next;

}e[MN*2];

int head[MN];

inline void add(int u,int v,int w){

    e[++top]=(Edge){u,v,w,head[u]};

    head[u]=top;

}

struct node{

    int x,dis;

    bool operator < (const node a) const{

        return dis>a.dis;

    }

};

int dis[MN]; bool vis[MN];

priority_queue<node> q;

void dijkstra(int x){

    while(!q.empty())q.pop();

    memset(dis,0x3f,sizeof(dis));

    dis[x]=0; q.push((node){x,0});

    while(!q.empty()){

        node now=q.top(); q.pop();

        if(vis[now.x])continue;

        vis[now.x]=true;

        for(reg int i=head[now.x];i;i=e[i].next){

            int v=e[i].v;

            if(dis[v]>dis[now.x]+e[i].w){

                dis[v]=dis[now.x]+e[i].w;

                q.push((node){v,dis[v]});

            }

        }

    }

}

int main(){

    scanf("%d%d%d",&n,&m,&s);

    for(reg int i=1,u,v,w;i<=m;++i){

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w);

    }

    dijkstra(s);

    for(reg int i=1;i<=n;++i){

        printf("%d ",dis[i]);

    }

    return 0;

}

Floyd

memset(dis,0x3f,sizeof(dis));

for(int i=1;i<=n;i++) dis[i][i]=0;

for(int k=1;k<=n;k++)

 for(int i=1;i<=n;i++)

  for(int j=1;j<=n;j++)

   dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

关于 memset的用法

依据 CC 4.0 BY-SA 版权协议转自 CSDN:fill 和 memset 函数详细说！（以及其中的 inf=0x3f3f3f3f 给 int 型赋值）【c++】

fill 函数：

在头文件<algorithm>中
按照单元赋值，即将一个区间中的元素都赋同一个值

fill(arr, arr + n, 要填入的内容）;   //普通数组

fill(v.begin(), v.end(), -1);       //vector

fill(f[0], f[0]+N*N, 要填入的内容）;    //二维数组

fill 应该是不可以给三维数组赋初值的（测试了一下），你们也可以尝试一下。（在之前写代码的时候想用，发现用不了）

memset 函数：

在头文件<cstring>中
按照字节填充某字符

因为 memset 函数按照字节填充，所以一般 memset 只能用来填充 char 型数组，（因为只有 char 型占一个字节）如果填充 int 型数组，除了 \(0\) 和-1，其他的不能。因为只有 00000000 = 0，-1 同理，如果我们把每一位都填充「1」，会导致变成填充入“11111111”。

理论上只能初始化为 \(0\) 和 \(-1\)，但是！

memset() 函数还能将 int 型数组初始化为 INF(0x3f3f3f3f)

以下内容参考自：https://blog.csdn.net/Karen_Yu_/article/details/78660591

首先来说说 inf=0x3f3f3f3f:

0x3f3f3f3f 的十进制是 \(1061109567\)，也就是 \(10^9\) 级别的（和 0x7fffffff（32-bit int 的最大值）一个数量级），而一般场合下的数据都是小于 \(10^9\) 的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。

另一方面，由于一般的数据都不会大于 \(10^9\)，所以当我们把无穷大加上一个数据时，它并不会溢出（这就满足了「无穷大加一个有穷的数依然是无穷大」），事实上 0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过 32-bit int 的表示范围，所以 0x3f3f3f3f 还满足了我们“无穷大加无穷大还是无穷大”的需求。

最大好处：

如果我们想要将某个数组清零，我们通常会使用 memset(a,0,sizeof(a))，但是当我们想将某个数组全部赋值为无穷大时（例如解决图论问题时邻接矩阵的初始化），就不能使用 memset 函数了，因为 memset 是按字节操作的，它能够对数组清零是因为 \(0\) 的每个字节都是 \(0\)，现在好了，如果我们将无穷大设为 0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f 的每个字节都是 0x3f！

所以要把一段整型数组全部置为无穷大，我们只需要 memset(a,INF,sizeof(a))。

编程中无穷大的设定：（主要介绍优点）

很多人可能设为 0x7fffffff, 这个数的确是 32-bit int 的最大值，符号位为 \(0\)，其他的都是 \(1\)

但在很多情况下，0x7fffffff 会出现错误，比如溢出，这样两个无穷大数相加会变成负数，还有如在做 dijkstra 求最短路时，当做松弛操作，判断 if(d[u]+w[u][v]<d[v]) d[v]=d[u]+w[u][v] 时，若 \(u\) 到 \(v\) 没有路径，w[u][v]=0x7fffffff，这样 d[u]+w[u][v] 会变成负数，这就产生了错误。

为了尽量避免以上的错误，我们可以改变无穷大的设定，可以将 0x3f3f3f3f 设为无穷大，0x3f3f3f3f 的 \(10\) 进制表示为 \(1061109567\)，这个数已达到 \(10^9\)，足以表示无穷大，又 0x3f3f3f3f+0x3f3f3f3f=2122219134，满足无穷大+无穷大仍为无穷大

当把无穷大设为 0x3f3f3f3f 时，在做初始化时也很方便，比如在初始化数组 a 时，可以使用

memset(a,0x3f,sizeof(a))，因为 0x3f3f3f3f 的每个字节都是 0x3f，如果使用 0x7fffffff，需要循环赋值，耗费更多时间。

#include <cstring>

#define inf 0x3f3f3f3f

//#define memset(a,b) memset(a,b,sizeof(a))

using namespace std;

int main(){

    int a[20];

    memset(a,inf,sizeof(a));

    memset(a,0x3f,sizeof(a));

    return 0;

}

以上两种方式都一样（亲测有效）。

P3383 【模板】线性筛素数

#include<cstdio>

#define reg register

using namespace std;

const long N=10000005;

long prime[N],num_prime;

bool isNotPrime[N];

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    isNotPrime[0]=isNotPrime[1]=1;

    for(reg int i=2;i<=n;++i){

        if(!isNotPrime[i])prime[num_prime++]=i;

        for(reg int j=0;j<num_prime && i*prime[j]<=n;++j){

            isNotPrime[i*prime[j]]=true;

            if(!(i%prime[j]))break;

        }

    }

    for(reg int i=0,x;i<m;++i){

        scanf("%d",&x);

        if(isNotPrime[x])printf("No\n");

        else printf("Yes\n");

    }

    return 0;

}

ST 表

#include<cstdio>

#include<algorithm>

#define reg register

using namespace std;

const long N=100005;

int a[N],f[N][21],log[N],d[21];

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    log[0]=-1;d[0]=1;//!漏

    for(reg int i=1;i<=n;++i){

//        scanf("%d",a+i);

        scanf("%d",&f[i][0]);

        log[i]=log[i>>1]+1;

    }

    for(reg int i=0;i<=21;++i)d[i]=1<<i;

    for(reg int i=1;i<=21 && n>=d[i];++i){

        for(reg int l=1;l<=n-d[i]+1;++l){

            f[l][i]=max(f[l][i-1],f[l+d[i-1]][i-1]);

        }

    }

    reg int l,r,len;

    while(m--){

        scanf("%d%d",&l,&r);

        len=log[r-l+1];

        printf("%d\n",max(f[l][len],f[r-d[len]+1][len]));

    }

    return 0;

}

巴特西