【置顶】模板集合

2018-03-06 22:10:19


退役后的某天我复习堆得时候,发现以前写的代码真的是太丑了……
于是决定再再再整一个模板集合
(洛谷博客没有代码折叠不太方便啊……


emacs配置:

(setq-default tab-width 4)
(setq-default c-basic-offset 4)
(global-linum-mode t)

vim配置:

set number
set ts=4
set sw=4
set smarttab
color desert
syntax on
set cindent

(小根)堆:

int hp[1100000],ht=0;
void ist(int z){
    int x;  hp[x=(++ht)]=z;//最小元素为1比为0好写不知道哪里去了!
    while(x!=1 && hp[x]<hp[x>>1])  swap(hp[x],hp[x>>1]),x>>=1;
}
void dlt(){
    hp[1]=hp[ht--];
    int x=1,mxid=1;
    for(;;){
        mxid=x;
        if((x<<1)<=ht && hp[x<<1]<hp[mxid])  mxid=(x<<1);//判断是否超出堆的大小不要丢
        if((x<<1|1)<=ht && hp[x<<1|1]<hp[mxid])  mxid=(x<<1|1);
        if(mxid==x)  break;
        swap(hp[mxid],hp[x]);  x=mxid;
    }
}

dinic:

int lvl[11000];
int q[11000],hd=0;
bool gtlvl(){
    memset(lvl,0,sizeof(lvl));
    lvl[q[hd=1]=s]=1;
    //这里lvl[s]好像不能设成0,因为下面mxflw判断lvl的时候好像会把已经挂成0的点通到lvl为1的点上
    for(int k=1;k<=hd;++k)
        for(int i=lk[q[k]];i;i=e[i].nxt)if(e[i].v && !lvl[e[i].y])
            lvl[e[i].y]=lvl[q[k]]+1,q[++hd]=e[i].y;
    return lvl[t];
}
int mxflw(int x,int y){
    if(x==t)  return y;
    int flw=0,bwl=0;
    for(int i=lk[x];i && bwl<y;i=e[i].nxt)if(e[i].v && lvl[e[i].y]==lvl[x]+1)
        if((flw=mxflw(e[i].y,min(e[i].v,y-bwl))))
            e[i].v-=flw,e[e[i].rvs].v+=flw,bwl+=flw;
    if(!bwl)  lvl[x]=0;
    return bwl;
}
int dnc(){
    int flw=0,bwl=0;
    while(gtlvl())while((flw=mxflw(s,oo)))  bwl+=flw;
    return bwl;
}