各类常见模板更新（不定期更新）-白红宇

各类常见模板更新（不定期更新）

阅读量：5133 次

发布时间：2019-06-13

本文共 6801 字，大约阅读时间需要 22 分钟。

　　俗话说得好：模板敲得好，NOIP炸不了。

　　因此为了防止比赛时想到了题解而敲不出来的情况，我们要坚持刷模板。

　　（争取每次上线的话打1~2个吧）

　　（排名顺序没有任何意义，想到什么写什么）

　　SPFA（对应题目Luogu P3371 【模板】单源最短路径）

#include
     
      #include
      
       using namespace std;const int N=10005,INF=2147483647;vector 
       
         a[N],l[N];int n,m,s,dis[N],i,x,y,z,q[N*20+10];bool f[N];inline void read(int &x){    x=0; char ch=getchar(); int flag=1;    while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); }    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    x*=flag;}int main(){    read(n); read(m); read(s);    for (i=1;i<=m;++i)    {        read(x); read(y); read(z);        a[x].push_back(y); l[x].push_back(z);    }    for (i=1;i<=n;++i)    dis[i]=INF;    dis[s]=0; f[s]=1; q[1]=s;    int head=0,tail=1;    while (head
        
         dis[now]+l[now][i])            {                dis[k]=dis[now]+l[now][i];                if (!f[k])                {                    f[k]=1;                    q[++tail]=k;                }            }        }    }    for (i=1;i<=n;++i)    printf("%d ",dis[i]);    return 0;}

　　Dijstra（堆优化）（对应题目Luogu P3371 【模板】单源最短路径）

#include
     
      #include
      
       #include
       
        using namespace std;const int N=10005,INF=2147483647;vector 
        
          a[N],l[N];struct data{    int num,s;    bool operator < (const data &a) const    {        return a.s
         
           small;int n,m,s,dis[N],i,x,y,z,q[N*20+10];bool f[N];inline void read(int &x){    x=0; char ch=getchar(); int flag=1;    while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); }    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    x*=flag;}int main(){    read(n); read(m); read(s);    for (i=1;i<=m;++i)    {        read(x); read(y); read(z);        a[x].push_back(y); l[x].push_back(z);    }    for (i=1;i<=n;++i)    dis[i]=INF;    dis[s]=0;    small.push((data){s,0});    while (!small.empty())    {        int now=small.top().num; small.pop();        if (f[now]) continue;        f[now]=1;        for (i=0;i
          
           dis[now]+l[now][i]) { dis[k]=dis[now]+l[now][i]; small.push((data){k,dis[k]}); } } } for (i=1;i<=n;++i) printf("%d ",dis[i]); return 0;}

　　线段树（朴素Lazytag）（对应题目 Luogu P3372 【模板】线段树 1）

#include
     
      using namespace std;typedef long long LL;const int N=100005;LL seg[N*4+10],add[N*4+10],i,n,m,a[N],x,y,z;inline void read(LL &x){    x=0; char ch=getchar(); int flag=1;    while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); }    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    x*=flag;}inline void write(LL x){    if (x/10) write(x/10);    putchar(x%10+'0');}inline void up(LL root) { seg[root]=seg[root*2]+seg[root*2+1]; }inline void down(LL root,LL l,LL r){    if (add[root])    {        add[root*2]+=add[root];        add[root*2+1]+=add[root];        seg[root*2]+=add[root]*l;        seg[root*2+1]+=add[root]*r;        add[root]=0;    }}inline void build(LL root,LL l,LL r){    if (l==r) seg[root]=a[l]; else    {        int mid=l+r>>1;        build(root*2,l,mid);        build(root*2+1,mid+1,r);        up(root);    }}inline void change(LL root,LL l,LL r,LL ql,LL qr,LL v){    if (l>=ql&&r<=qr)     {        add[root]+=v;        seg[root]+=v*(r-l+1);    } else    {        int mid=l+r>>1;        down(root,mid-l+1,r-mid);        if (ql<=mid) change(root*2,l,mid,ql,qr,v);        if (mid
      
       =ql&&r<=qr) return seg[root]; else    {        int mid=l+r>>1;        down(root,mid-l+1,r-mid);        LL res=0;        if (ql<=mid) res+=query(root*2,l,mid,ql,qr);        if (mid

　　RMQ（ST表）（对应题目 P3865 【模板】ST表）

#include
     
      using namespace std;const int N=100005,P=20;int f[N][P],n,m,x,y,i,j;inline void read(int &x){    x=0; char ch=getchar(); int flag=1;    while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); }    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    x*=flag;}inline void write(int x){    if (x/10) write(x/10);    putchar(x%10+'0');}inline int max(int a,int b) { return a>b?a:b; }int main(){    read(n); read(m);    for (i=1;i<=n;++i)    read(f[i][0]);    for (j=1;j

　　K短路（Astar）（对应题目P2483 【模板】k短路（[SDOI2010]魔法猪学院））

// luogu-judger-enable-o2#include
     
      #include
      
       using namespace std;typedef double DB;const int N=5005;struct data{    int num;    DB s;    bool operator <(const data &a) const     {        return a.s
       
         small;priority_queue 
        
          tree;vector 
         
           a[N],b[N];vector 
          
            l[N],rl[N];int n,m,i,x,y,ans;DB z,tot,dis[N],sum;bool vis[N];inline void read(int &x){ x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();}int main(){ read(n); read(m); scanf("%lf",&tot); for (i=1;i<=m;++i) { read(x); read(y); scanf("%lf",&z); a[x].push_back(y); l[x].push_back(z); b[y].push_back(x); rl[y].push_back(z); } for (i=1;i<=n;++i) dis[i]=1e9; dis[n]=0; small.push((data){n,0}); while (!small.empty()) { int now=small.top().num; small.pop(); if (vis[now]) continue; vis[now]=1; for (i=0;i
           
            dis[now]+rl[now][i]) { dis[k]=dis[now]+rl[now][i]; small.push((data){k,dis[k]}); } } } tree.push((Astar){ 1,0,dis[1]}); while (!tree.empty()) { int now=tree.top().num; DB temp=tree.top().s; tree.pop(); if (now==n) { if (sum+temp>tot) { printf("%d",ans); return 0; } else ans++,sum+=temp; } for (i=0;i

　　Dinic (对应题目 P3376 【模板】网络最大流）

#include
     
      #include
      
       using namespace std;const int N=10005,M=100005,INF=2e9;struct edge{    int to,next,c;}e[M*2];int q[N],head[N],dep[N],n,m,s,t,i,x,y,z,k=-1;inline void read(int &x){    x=0; char ch=getchar();    while (ch<'0'||ch>'9') ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();}inline void add(int x,int y,int z){    e[++k].to=y; e[k].c=z; e[k].next=head[x]; head[x]=k;}inline int min(int a,int b){    return a
       
        0)        {            dep[e[i].to]=dep[now]+1;            q[++T]=e[i].to;        }    }    return dep[t]?1:0;}inline int DFS(int now,int dist){    if (now==t) return dist;    int res=0;    for (int i=head[now];i!=-1&&dist;i=e[i].next)    if (dep[e[i].to]==dep[now]+1&&e[i].c>0)    {        int dis=DFS(e[i].to,min(e[i].c,dist));        dist-=dis; res+=dis;        e[i].c-=dis; e[i^1].c+=dis;    }    if (!res) dep[now]=0;    return res;}inline int Dinic(int s,int t){    int sum=0;    while (BFS(s,t)) sum+=DFS(s,INF);    return sum;}int main(){    memset(e,-1,sizeof(e));    memset(head,-1,sizeof(head));    read(n); read(m); read(s); read(t);    for (i=1;i<=m;++i)    {        read(x); read(y); read(z);        add(x,y,z); add(y,x,0);    }    printf("%d",Dinic(s,t));    return 0;}