rainman's blog

学海无涯,回头是岸

模板整理

主要就是整理一下常见的算法模板,个人使用。

线性筛素数

给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)

//code by ushio
#include<cstdio>
using namespace std;

const int MAXN = 10000100;
bool composite[MAXN];
int prime[MAXN],tail;

void get_prime(int n)
{
    composite[0]=true;
    composite[1]=true;
    for(int i=2;i<=n;i++)
    {
        if(!composite[i])prime[tail++]=i;
        for(int j=0;j<tail&&i*prime[j]<=n;j++)
        {
            composite[i*prime[j]]=true;
            if(!(i%prime[j]))break;
        }
    }
}

int main()
{
    int n,t,temp;
    scanf("%d%d",&n,&t);
    get_prime(n);

    for(int i=1;i<=t;i++){
        scanf("%d",&temp);
        if(composite[temp])puts("No");
        else puts("Yes");
    }

    return 0;
}

并查集

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=10010;
int uset[MAXN];

void makeset(int size){
    for(int i=0;i<size;i++)uset[i]=i;
}

int find(int x){
    if(x!=uset[x])uset[x]=find(uset[x]);
    return uset[x];
}

void unionset(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    uset[x]=y;
}

int main()
{
    int n,m; cin>>n>>m;
    makeset(n+1);

    int z,x,y;
    while(m--)
    {
        scanf("%d%d%d",&z,&x,&y);
        if(z==1)unionset(x,y);
        else if(z==2){
            if(find(x)==find(y))
            printf("Y\n");
            else printf("N\n");
        }
    }

    return 0;
}

最小生成树

给出一个无向图,求出最小生成树,如果该图不连通,则输出orz

输入格式:

第一行包含两个整数N、M,表示该图共有N个结点和M条无向边。(N<=5000,M<=200000)

接下来M行每行包含三个整数Xi、Yi、Zi,表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式:

输出包含一个数,即最小生成树的各边的长度之和;如果该图不连通则输出orz

//kruscal
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN = 5000+10;
const int MAXM = 200000+10;
struct Edge{int u,v,w;}edge[MAXM];
int uset[MAXN],n,m,ans;

int find(int x){
    if(uset[x]!=x)uset[x]=find(uset[x]);
    return uset[x];
}

void unionset(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    uset[x]=y;
}

bool cmp(Edge x,Edge y){return x.w<y.w;}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        edge[i].u=x;
        edge[i].v=y;
        edge[i].w=z;
    }

    sort(edge+1,edge+1+m,cmp);
    for(int i=0;i<=n;i++)uset[i]=i;

    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        int x=find(edge[i].u);
        int y=find(edge[i].v);
        if(x==y)continue;
        ans+=edge[i].w;
        unionset(x,y);
        if(++cnt==n-1)break;
    }

    if(cnt<n-1)printf("orz");
    else printf("%d",ans);
    return 0;
}

单源最短路径

给出一个有向图,请输出从某一点出发到所有点的最短路径长度。

输入格式:

第一行包含三个整数N、M、S,分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi,分别表示第i条有向边的出发点、目标点和长度。

输出格式:

一行,包含N个用空格分隔的整数,其中第i个整数表示从点S出发到点i的最短路径长度(若S=i则最短路径长度为0,若从点S无法到达点i,则最短路径长度为2147483647)

$SPFA$

//code by ushio
#include<bits/stdc++.h>
#define MAXM 500010
#define MAXN 10010
#define INF 2147483647
using namespace std;

int n,m,s,dis[MAXN];
bool inq[MAXN];
struct Edge{int v,w,next;}edge[MAXM];
int tot,head[MAXN];

inline void addedge(int x,int y,int z){
    edge[++tot].v=y;
    edge[tot].w=z;
    edge[tot].next=head[x];
    head[x]=tot;
}

void spfa()
{
    queue<int> qwq;
    for(int i=1;i<=n;i++)dis[i]=INF;

    qwq.push(s);
    dis[s]=0;inq[s]=true;

    while(!qwq.empty())
    {
        int x=qwq.front();
        qwq.pop(); inq[x]=false;

        for(int i=head[x];i;i=edge[i].next){
            int y=edge[i].v;
            if(dis[y]>dis[x]+edge[i].w){
                dis[y]=dis[x]+edge[i].w;
                if(!inq[y]){qwq.push(y);inq[y]=true;}
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }

    spfa();

    for(int i=1;i<=n;i++)
     if(s==i)printf("0 ");
     else printf("%d ",dis[i]);

    return 0;
}

$Dijkstra$

//code by ushio
#include<cstdio>
#include<queue>
#define MAXM 200010
#define MAXN 100010
using namespace std;

const int INF =2147483647;
int n,m,s,dis[MAXN];
bool done[MAXN];
int tot,head[MAXN];
struct Edge{int v,w,next;}edge[MAXM];

inline void addedge(int x,int y,int z)
{
    edge[++tot].v=y;
    edge[tot].w=z;
    edge[tot].next=head[x];
    head[x]=tot;
}

struct node{
    int u,dist;
    bool operator<(const node& v)const{
        return dist>v.dist;
    }
};

priority_queue<node> qwq;
inline void dijkstra()
{
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[s]=0;
    qwq.push((node){s,0});

    while(!qwq.empty())
    {
        node front=qwq.top(); qwq.pop();
        int u=front.u,dist=front.dist;
        if(done[u])continue;
        done[u]=true;
        for(int i=head[u];i;i=edge[i].next)
        {
            int y=edge[i].v,z=edge[i].w;
            if(dis[u]+z<dis[y])
            {
                dis[y]=dis[u]+z;
                qwq.push((node){y,dis[y]});
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }

    dijkstra();

    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
    return 0;
}

树状数组

已知一个数列,你需要进行下面两种操作:

1.将某一个数加上x

2.求出某区间每一个数的和

//code by ushio
#include<cstdio>
#define lowbit(x) (x&(-x))
using namespace std;

const int MAXN = 500010;
int c[MAXN],n,m;

inline int sum(int i)
{
    int s=0;
    while(i>0){
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}

inline void update(int i,int value)
{
    while(i<=n){
        c[i]+=value;
        i+=lowbit(i);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int temp;scanf("%d",&temp);
        update(i,temp);
    }

    for(int i=1;i<=m;i++)
    {
        int flag,x,y;
        scanf("%d%d%d",&flag,&x,&y);
        if(flag==1) update(x,y);
        else printf("%d\n",sum(y)-sum(x-1));
    }

    return 0;
}

已知一个数列,你需要进行下面两种操作:

1.将某区间每一个数数加上x

2.求出某一个数的值

//code by ushio
#include<cstdio>
#define lowbit(x) (x&(-x))
using namespace std;

const int MAXN = 500010;
int c[MAXN],n,m,pre,now;

inline int sum(int i)
{
    int s=0;
    while(i>0){
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}

inline void update(int i,int value)
{
    while(i<=n){
        c[i]+=value;
        i+=lowbit(i);
    }
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&now);
        update(i,now-pre);
        pre=now;
    }

    for(int i=1;i<=m;i++)
    {
        int flag,x;
        scanf("%d%d",&flag,&x);
        if(flag==1)
        {
            int y,k;scanf("%d%d",&y,&k);
            update(x,k);update(y+1,-k);
        }
        else printf("%d\n",sum(x));
    }

    return 0;
}

最近公共祖先

//code by rainman
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

const int MAXN = 500010;
const int MAXM = MAXN-1;
int max0,n,m,tot,head[MAXN];
int fa[MAXN][25],dep[MAXN],s;
struct Edge{int v,next;}edge[MAXM<<1];

inline void addedge(int x,int y)
{
    edge[++tot].v=y;
    edge[tot].next=head[x];
    head[x]=tot;
}

void lcainit(int x)
{
    for(int i=1;i<=max0;i++)
    if(fa[x][i-1])fa[x][i]=fa[fa[x][i-1]][i-1];
    else break;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].v;
        if(y!=fa[x][0]){
            fa[y][0]=x;
            dep[y]=dep[x]+1;
            lcainit(y);
        }
    }
}

inline int lca(int u,int v)
{
    if(dep[u]<dep[v])swap(u,v);
    int delta=dep[u]-dep[v];
    for(int x=0;x<=max0;x++)
    if((1<<x)&delta)u=fa[u][x];
    if(u==v)return u;
    for(int x=max0;x>=0;x--)
    if(fa[u][x]!=fa[v][x]){
        u=fa[u][x];
        v=fa[v][x];
    }
    return fa[u][0];
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    max0=(int)(log(n)/log(2))+3;

    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        addedge(x,y);addedge(y,x);
    }

    lcainit(s);

    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }

    return 0;
}

强连通分量缩点

题目描述:https://www.luogu.org/problemnew/show/P3387

//code by rainman
#include<cstdio>
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
using namespace std;

const int MAXN =1e4+10;
const int MAXM =1e5+10;
int head[MAXN],tot,head2[MAXN],tot2;
int dfn[MAXN],low[MAXN],num,W[MAXN];
int cnt,id[MAXN],w[MAXN],f[MAXN];
int stac[MAXN],n,m,top,in[MAXN];
struct Edge{int v,next;}edge[MAXM];
struct Edge2{int v,next;}edge2[MAXM];
bool ins[MAXN];

inline void addedge(int x,int y)
{
    edge[++tot].v=y;
    edge[tot].next=head[x];
    head[x]=tot;
}

inline void addedge2(int x,int y)
{
    edge2[++tot2].v=y;
    edge2[tot2].next=head2[x];
    head2[x]=tot2;
}

void tarjan(int x)
{
    dfn[x]=low[x]=++num;  //time tag
    stac[++top]=x; ins[x]=true;
    for(int i=head[x];i;i=edge[i].next)
    if(!dfn[edge[i].v])
    {
        tarjan(edge[i].v);
        low[x]=MIN(low[x],low[edge[i].v]);
    }
    else if(ins[edge[i].v])
    low[x]=MIN(low[x],dfn[edge[i].v]);

    if(dfn[x]==low[x])
    {
        ++cnt; int y;
        do{
            y=stac[top--],ins[y]=false;
            id[y]=cnt;
            W[cnt]+=w[y];
        }while(x!=y);
    } 
}

inline void input()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
    }
}

int dfs(int x)
{
    if(f[x])return f[x];
    int temp=0;
    for(int i=head2[x];i;i=edge2[i].next){
        int y=edge2[i].v;
        temp=MAX(temp,dfs(y));
    }
    f[x]=temp+W[x];
    return f[x];
}

int main()
{
    input();
    for(int i=1;i<=n;i++)
    if(!dfn[i])tarjan(i);

    for(int x=1;x<=n;x++)
    for(int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].v;
        if(id[x]!=id[y]){
            addedge2(id[x],id[y]);
            in[id[y]]++;
        }
    }

    int ans=0;
    for(int i=1;i<=cnt;i++)
        if(!in[i]){
            dfs(i);
            ans=MAX(ans,f[i]);
        }

    printf("%d",ans);
    return 0;
}

2019-06-10 17:43:08 in 算法