【置顶】模板集合
cdcq
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
```
（小根）堆：
```cpp
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：
```cpp
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;
}
```