博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
noip考前模板复习
阅读量：5323 次
发布时间：2019-06-14

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

网络流

Dinic(搭配飞行员)

//Serene#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=100+10,maxs=maxn*maxn+2*maxn;int n,m,S,T;int aa;char cc;int read() { aa=0;cc=getchar(); while(cc<'0'||cc>'9') cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa;}struct Node{ int x,y,cap,flow; Node(){} Node(int x,int y,int cap):x(x),y(y),cap(cap){}}node[maxs];int fir[maxn],nxt[maxs],e=1,cur[maxn];void add(int x,int y,int z) { node[++e]=Node(x,y,z); nxt[e]=fir[x];fir[x]=e; node[++e]=Node(y,x,0); nxt[e]=fir[y];fir[y]=e;}int dis[maxn],zz[maxn];bool bfs() { int s=1,t=0,x,y,z; memset(dis,-1,sizeof(dis)); memset(zz,0,sizeof(zz)); dis[S]=0; zz[++t]=S; while(s<=t) { x=zz[s++]; for(y=fir[x];y;y=nxt[y]) { if(node[y].flow>=node[y].cap||dis[z=node[y].y]!=-1) continue; dis[z]=dis[x]+1; zz[++t]=z; } } return dis[T]!=-1;}int dfs(int pos,int maxf) { if(pos==T||!maxf) return maxf; int rs=0,now,z; for(int &y=cur[pos];y;y=nxt[y]) { if(node[y].flow>=node[y].cap||dis[z=node[y].y]!=dis[pos]+1) continue; now=dfs(z,min(node[y].cap-node[y].flow,maxf)); node[y].flow+=now; node[y^1].flow-=now; rs+=now; maxf-=now; } if(!rs) dis[pos]=-1; return rs;}int Dinic() { int rs=0; while(bfs()) { memcpy(cur,fir,sizeof(fir)); rs+=dfs(S,0x3f3f3f3f); } return rs;}int main() { n=read(); m=read(); S=n+1; T=S+1; int x,y; for(int i=1;i<=m;++i) add(S,i,1); for(int i=m+1;i<=n;++i) add(i,T,1); while(scanf("%d%d",&x,&y)==2) add(x,y,1); printf("%d",Dinic()); return 0;}

MCMF(餐巾计划)

//Serene#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=2000+10,maxm=4*maxn,INF=0x3f3f3f3f;int n,P,M,F,N,R,S,T;int aa;char cc;int read() { aa=0;cc=getchar(); while(cc<'0'||cc>'9') cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa;}struct Node{ int x,y,cap,flow,w; Node(){} Node(int x,int y,int cap,int w):x(x),y(y),cap(cap),w(w){}}node[2*maxm];int fir[maxn],nxt[2*maxm],e=1;void add(int x,int y,int z,int w) { node[++e]=Node(x,y,z,w); nxt[e]=fir[x];fir[x]=e; node[++e]=Node(y,x,0,-w);nxt[e]=fir[y];fir[y]=e;}int from[maxn],zz[maxn],dis[maxn];bool vis[maxn];bool spfa() { int s=1,t=0,x,y,z; memset(dis,0x3f3f3f3f,sizeof(dis)); memset(zz,0,sizeof(zz)); zz[++t]=S;dis[S]=0;vis[S]=1; while(s<=t) { x=zz[s%maxn];s++;vis[x]=0; for(y=fir[x];y;y=nxt[y]) { if(node[y].flow>=node[y].cap||dis[z=node[y].y]<=dis[x]+node[y].w) continue; dis[z]=dis[x]+node[y].w; from[z]=y; if(!vis[z]) { vis[z]=1;t++; zz[t%maxn]=z; } } } return dis[T]!=INF;}int MCMF() { int rs=0,now; while(spfa()) { now=INF; for(int i=T;i!=S;i=node[from[i]].x) now=min(now,node[from[i]].cap-node[from[i]].flow); for(int i=T;i!=S;i=node[from[i]].x) { node[from[i]].flow+=now; node[from[i]^1].flow-=now; rs+=node[from[i]].w*now; } } return rs;}int main() { n=read(); S=2*n+1;T=S+1; int x; P=read();M=read();F=read();N=read();R=read(); for(int i=1;i<=n;++i) { add(S,i+n,INF,P); if(i+1<=n) add(i,i+1,INF,0); if(i+M<=n) add(i,i+M+n,INF,F); if(i+N<=n) add(i,i+N+n,INF,R); } for(int i=1;i<=n;++i) { x=read(); add(S,i,x,0); add(i+n,T,x,0); } printf("%d",MCMF()); return 0;}

最短路

SPFA(SLF)

//Serene#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=1e4+10,maxm=5e5+10,INF=2147483647;int n,m,S;int aa,ff;char cc;int read() { aa=0;ff=1;cc=getchar(); while(cc<'0'||cc>'9') { if(cc=='-') ff=-1; cc=getchar(); } while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa*ff;}int fir[maxn],nxt[maxm],to[maxm],v[maxm],e=0;void add(int x,int y,int z) { to[++e]=y;nxt[e]=fir[x];fir[x]=e;v[e]=z;}int dis[maxn],zz[maxn];bool vis[maxn];void spfa() { for(int i=1;i<=n;++i) dis[i]=INF; int s=1,t=0,x,y,z,tot=1; dis[S]=0; zz[++t]=S; vis[S]=1; while(tot) { x=zz[s];s=(s+1)%maxn;vis[x]=0;tot--; for(y=fir[x];y;y=nxt[y]) { if(dis[z=to[y]]<=dis[x]+v[y]) continue; dis[z]=dis[x]+v[y]; if(!vis[z]) { vis[z]=1;tot++; if(dis[z]<=dis[zz[s]]) {s=(s-1+maxn)%maxn;zz[s]=z;} else {t=(t+1)%maxn;zz[t]=z;} } } }}int main() { n=read();m=read(); S=read(); int x,y,z; for(int i=1;i<=m;++i) { x=read();y=read();z=read(); add(x,y,z); } spfa(); for(int i=1;i<=n;++i)printf("%d ",dis[i]); return 0;}

Dijkstra(堆优)

//Serene#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn=1e4+10,maxm=5e4+10,INF=0x3f3f3f3f;int n,m,k,S,T,ans=INF;int aa;char cc;int read() { aa=0;cc=getchar(); while(cc<'0'||cc>'9') cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa;}int fir[maxn],nxt[2*maxm],to[2*maxm],v[2*maxm],e=0;void add(int x,int y,int z) { to[++e]=y;nxt[e]=fir[x];fir[x]=e;v[e]=z; to[++e]=x;nxt[e]=fir[y];fir[y]=e;v[e]=z;}struct Di{ int x,y,d; Di(){} Di(int x,int y,int d):x(x),y(y),d(d){} bool operator < (const Di& a) const{ return d > a.d; }};priority_queue
           
             G;int dis[maxn][13];void Dijkstra() { memset(dis,0x3f3f3f3f,sizeof(dis)); dis[S][0]=0; G.push(Di(S,0,0)); int x,y,z,l,d; while(!G.empty()) { x=G.top().x;l=G.top().y;d=G.top().d; G.pop(); if(d!=dis[x][l]) continue; for(y=fir[x];y;y=nxt[y]) { if(dis[z=to[y]][l]>dis[x][l]+v[y]) { dis[z][l]=dis[x][l]+v[y]; G.push(Di(z,l,dis[z][l])); } if(l
            
             dis[x][l]) { dis[z][l+1]=dis[x][l]; G.push(Di(z,l+1,dis[z][l+1])); } } }}int main() { n=read();m=read();k=read(); S=read()+1;T=read()+1; int x,y,z; for(int i=1;i<=m;++i) { x=read()+1;y=read()+1;z=read(); add(x,y,z); } Dijkstra(); for(int i=0;i<=k;++i) ans=min(ans,dis[T][i]); printf("%d",ans); return 0;}

最小生成树

Kruskal

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=5000+10,maxm=2e5+10;int n,m,ans;int aa;char cc;int read() { aa=0;cc=getchar(); while(cc<'0'||cc>'9') cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa;}struct Node{ int x,y,z;}node[maxm];bool cmp(const Node& a,const Node& b) { return a.z

Prim

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
            using namespace std;const int maxn=5000+10,maxm=2e5+10;int n,m;int aa;char cc;int read() { aa=0;cc=getchar(); while(cc<'0'||cc>'9') cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa;}int fir[maxn],nxt[2*maxm],to[2*maxm],v[2*maxm],e=0;void add(int x,int y,int z) { to[++e]=y;nxt[e]=fir[x];fir[x]=e;v[e]=z; to[++e]=x;nxt[e]=fir[y];fir[y]=e;v[e]=z;}struct Node{ int x,d; Node(){} Node(int x,int d):x(x),d(d){} bool operator <(const Node& a) const { return d > a.d; }};priority_queue
           
             G;int dis[maxn];bool vis[maxn];void Prim() { memset(dis,0x3f3f3f3f,sizeof(dis)); dis[1]=0; G.push(Node(1,0)); int x,y,z,tot=0,rs=0; while(!G.empty()&&tot

二分图匹配

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=2000+10;int n1,n2,m,ans;int aa;char cc;int read() { aa=0;cc=getchar(); while(cc<'0'||cc>'9') cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa;}int fir[2*maxn],nxt[maxn*maxn],to[maxn*maxn],e=0;void add(int x,int y) { to[++e]=y;nxt[e]=fir[x];fir[x]=e; to[++e]=x;nxt[e]=fir[y];fir[y]=e;}int mch[2*maxn];bool vis[maxn];int expd(int pos) { int z; for(int y=fir[pos];y;y=nxt[y]) { if(vis[z=to[y]]) continue; vis[z]=1; if(!mch[z]||expd(mch[z])) { mch[z]=pos; return 1; } } return 0;}int main() { n1=read();n2=read();m=read(); int x,y; for(int i=1;i<=m;++i) { x=read();y=read(); if(x>n1||y>n2) continue; add(x,y+n1); } for(int i=1;i<=n1;++i) memset(vis,0,sizeof(vis)),ans+=expd(i); printf("%d",ans); return 0;}

排序

归并排序

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=4e4+10;int n,a[maxn],ans;int aa,ff;char cc;int read() { aa=0;cc=getchar();ff=1; while(cc<'0'||cc>'9') { if(cc=='-') ff=-1; cc=getchar(); } while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa*ff;}int c[maxn];void msort(int l,int r) { if(l==r) return; int mid=(l+r)>>1; msort(l,mid);msort(mid+1,r); int pos1=l,pos2=mid+1; for(int i=l;i<=r;++i) { if(pos2>r||(a[pos1]<=a[pos2]&&pos1<=mid)) c[i]=a[pos1++]; else { ans+=mid-pos1+1; c[i]=a[pos2++]; } } for(int i=l;i<=r;++i) a[i]=c[i];}int main() { n=read(); for(int i=1;i<=n;++i) a[i]=read(); msort(1,n); printf("%d",ans); return 0;}

字符串

KMP

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=1e6+10;int n,m,nt[maxn];char s[maxn],c[maxn];int main() { scanf("%s%s",s+1,c+1); n=strlen(s+1); m=strlen(c+1); c[m+1]='#';int pos; for(int i=2;i<=m;++i) { pos=nt[i-1]; while(pos&&c[pos+1]!=c[i]) pos=nt[pos]; nt[i]=c[pos+1]==c[i]? pos+1:0; } pos=0; for(int i=1;i<=n;++i) { while(pos&&s[i]!=c[pos+1]) pos=nt[pos]; if(s[i]==c[pos+1]) pos++; if(pos==m) printf("%d\n",i-m+1),pos=nt[pos]; } for(int i=1;i<=m;++i) printf("%d ",nt[i]); return 0;}

AC自动机

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=1e6+10;int n;char s[maxn];struct Node{ int son[27],fail,sum;}node[maxn/2];int t;void add() { int now=0,len=strlen(s+1),x; for(int i=1;i<=len;++i) { x=s[i]-'a'; if(!node[now].son[x]) node[now].son[x]=++t; now=node[now].son[x]; } node[now].sum++;}int zz[maxn];void bld() { int s=1,t=0,x,y; for(int i=0;i<26;++i) if(node[0].son[i]) zz[++t]=node[0].son[i]; while(s<=t) { x=zz[s++]; for(int i=0;i<26;++i) { y=node[x].son[i]; if(!y) node[x].son[i]=node[node[x].fail].son[i]; else node[y].fail=node[node[x].fail].son[i],zz[++t]=y; } }}void q() { int len=strlen(s+1),now=0,ans=0,x,y; for(int i=1;i<=len;++i) { x=s[i]-'a'; now=node[now].son[x]; for(y=now;y&&~node[y].sum;y=node[y].fail) ans+=node[y].sum,node[y].sum=-1; } printf("%d",ans);}int main() { scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%s",s+1); add(); } bld(); scanf("%s",s+1); q(); return 0;}

线性基

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define ll long longconst int maxn=50+10;ll n,h[maxn],now;ll aa;char cc;ll read() { aa=0;cc=getchar(); while(cc<'0'||cc>'9') cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa;}void add(ll x) { for(int i=50;~i;--i) if((x>>i)&1) { if(h[i]) x^=h[i]; else { h[i]=x; break; } }}int main() { n=read(); for(int i=1;i<=n;++i) add(read()); for(int i=50;~i;--i) if((now^h[i])>now) now^=h[i]; printf("%lld",now); return 0;}

矩阵快速幂

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define ll long longconst int maxn=5000+10;const ll mod=1e9+7;ll n,now[5]={0,2,2,10,32},mtx[5][5],f[5],d[5][5];void qf() { memset(f,0,sizeof(f)); for(int i=1;i<=4;++i) for(int k=1;k<=4;++k) (f[i]+=now[k]*mtx[k][i]%mod)%=mod; memcpy(now,f,sizeof(f));}void qd() { memset(d,0,sizeof(d)); for(int i=1;i<=4;++i) for(int j=1;j<=4;++j) for(int k=1;k<=4;++k) (d[i][j]+=mtx[i][k]*mtx[k][j]%mod)%=mod; memcpy(mtx,d,sizeof(d));}void qp(ll k) { while(k) { if(k&1) qf(); qd(); k>>=1; }}int main() { scanf("%lld",&n); mtx[1][1]=mtx[3][2]=mtx[4][3]=mtx[1][4]=1; mtx[2][4]=2; mtx[3][4]=mod-5; mtx[4][4]=4; qp(n-3); printf("%lld",now[2]); return 0;}

数据结构

树状数组区间修改区间查询

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define ll long longconst int maxn=1e5+10;ll n,m,a[maxn],g[maxn],h[maxn],ans;ll aa,ff;char cc;ll read() { aa=0;cc=getchar();ff=1; while(cc<'0'||cc>'9') { if(cc=='-') ff=-1; cc=getchar(); } while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa*ff;}void add(int pos,ll x,ll *sz) { while(pos<=n) { sz[pos]+=x; pos+=(pos&-pos); }}ll q(int pos,ll *sz) { ll rs=0; while(pos) { rs+=sz[pos]; pos-=(pos&-pos); } return rs;}int main() { n=read(); m=read(); int op;ll l,r,x; for(int i=1;i<=n;++i) { a[i]=read(); add(i,a[i]-a[i-1],g); add(i,(ll)(i-1)*(a[i]-a[i-1]),h); } for(int i=1;i<=m;++i) { op=read(); l=read(); r=read(); if(op==1) { x=read(); add(l,x,g);add(r+1,-x,g); add(l,(ll)(l-1)*x,h); add(r+1,(ll)r*(-x),h); } else { ans=r*q(r,g)-q(r,h)-(l-1)*q(l-1,g)+q(l-1,h); printf("%lld\n",ans); } } return 0;}

Tarjan

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=1e4+10,maxm=1e5+10;int n,m,v[maxn],totans;int aa;char cc;int read() { aa=0;cc=getchar(); while(cc<'0'||cc>'9') cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); return aa;}int fir[maxn],nxt[maxm],to[maxm],e=0;void add(int x,int y) { to[++e]=y;nxt[e]=fir[x];fir[x]=e;}int ff[maxn],nn[maxm],tt[maxm],ee=0,ind[maxn];void add2(int x,int y) { tt[++ee]=y;nn[ee]=ff[x];ff[x]=ee;ind[y]++;}int id[maxn],d,zz[maxn],t,top[maxn];int xd[maxn],sum[maxn],totd;bool vis[maxn],inz[maxn];void tj(int pos) { id[pos]=top[pos]=++d; vis[pos]=inz[pos]=1; zz[++t]=pos; int y,z; for(y=fir[pos];y;y=nxt[y]) { if(inz[z=to[y]]) top[pos]=min(top[pos],top[z]); if(vis[z]) continue; tj(z); top[pos]=min(top[pos],top[z]); } if(top[pos]==id[pos]) { totd++; while(t) { xd[y=zz[t]]=totd; sum[totd]+=v[y]; inz[y]=0; if(zz[t--]==pos) break; } }}int ans[maxn];void tp() { int s=1,t=0,x,y,z; for(int i=1;i<=totd;++i) if(!ind[i]) zz[++t]=i,ans[i]=sum[i]; while(s<=t) { x=zz[s++]; for(y=ff[x];y;y=nn[y]) { ind[z=tt[y]]--; ans[z]=max(ans[z],sum[z]+ans[x]); if(!ind[z]) zz[++t]=z; } }}int main() { n=read();m=read(); int x,y; for(int i=1;i<=n;++i) v[i]=read(); for(int i=1;i<=m;++i) { x=read();y=read(); add(x,y); } for(int i=1;i<=n;++i) if(!vis[i]) tj(i); for(int i=1;i<=n;++i) { for(y=fir[i];y;y=nxt[y]) if(xd[x=to[y]]!=xd[i]){ add2(xd[i],xd[x]); } } tp(); for(int i=1;i<=totd;++i) totans=max(totans,ans[i]); printf("%d",totans); return 0;}

转载于:https://www.cnblogs.com/Serene-shixinyi/p/7809509.html

你可能感兴趣的文章
java 注解 学习
查看>>
[leetcode]403. Frog Jump青蛙过河
查看>>
英语音节知识
查看>>
IEEE 802.15.4协议学习之MAC层
查看>>
AngularJS学习篇（十三）
查看>>
Tableau 学习资料
查看>>
中断和异常
查看>>
lucene 全文检索工具的介绍
查看>>
C# MD5-16位加密实例,32位加密实例
查看>>
无线点餐系统初步构思
查看>>
AJAX
查看>>
前端之CSS
查看>>
List注意点【修改】
查看>>
sqoop导入导出对mysql再带数据库test能跑通用户自己建立的数据库则不行
查看>>
拓扑排序的原理及其实现
查看>>
对StageWebView捕获位图时空白
查看>>
Provison Profile管理及存放路径
查看>>
shop--8.店铺列表展示--前端开发
查看>>
转：Can not issue data manipulation statements with executeQuery()错误解决
查看>>
详解C#委托，事件与回调函数（转）
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-28 05:48:41   当前IP: 18.217.10.200   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我