ACMICPC 模板大全集合手册

1 1 1 1 4 5 7 11 15 15 15 16 17 18 19 19 20 20 22 23 23 23 24 26 27 27 30 32 33 33 34 35 38 41 42 43 45 49 51 51 53 54 55 56 58 60 60 61 61 62 63 64 65 65 65 67 71 71 74 76 78 78 83 87 89 92 95 99 102 104 105 106 110 111 113 119 123 125 125 127 127 128 128 129 130 131 131 131 132 133 134 136 136 138 138 139 139 139 140 1403.2点、线段、 140 140 141 141 143 143 143 144 146 147 1484.1整数的因子分解 148 1484.1.2Prollard 149 1504.2乘法逆元 151 152 152 153 153 153 155 158 158 158 159 159 1604.6一些重要积性函数 162 162 163 164 165 166 166 167 167 168 170 170 171 171 172 173 173 174 174 174 175 176 177 177 177 178 178 179 183 183 184 185 185 187 189 191 193 195 201 201 202 202 203 204 204 205 205 206 206 209 210 214 214 214 214 214 214 215 215 215 215 215 216 216 216 216 216 217 217 218 218 218 218 218 219 219 219 219 219 220 220 220 220 220 222inttot,top,t;p[tot].to=b;head[a]=tot++;}voiddfs(intu){//dfs序fa[u]=-1;}top--;}}1.1.2树的重心p[tot].to=b;head[a]=tot++;p[tot].to=a;head[b]=tot++;}//非递归版DFSintans,id,n;vis[v]=1;st[++top]=p[i].to;}intr=p[i].to;}son[v]=sum+1;top--;ans=bal,id=v;}}//递归版DFSintv=p[i].to;}son[u]=sum+1;num=0;}}//BFS版vis[p[j].to]=1;}intans=1<<30,id;intv=p[j].to;}vis[st[i]]=0;son[st[i]]=sum+1;}1.1.3树的直径//树形dphead[a]=tot++;}voiddfs(intu,intfa){//过u的最长链max1[u]=max1[v]+p[i}elsemax2[u]=max(max}}res=max(res,max1[u]+m}//两次BFSq[++e]=u,dist[u]=0;}}//dist[]记录直径上各点到da的路径长度da=1;db=1;top=0;while(db!=da){st[top++]=db;db=//将st反转过来for(inti=0;i<(top-1)/2;i++)//搜侧链intl=0,r=dist[st[top-1]];//r直径的长度//l侧链的最大长度1.1.4树的点分治intbal[Maxn];//节点最多的子树intk;//统计树上距离小于k的点对}bal[u]=max(bal[u],sum-s}voiddfs(intu,intfa){//计算以u为根的子树节点到u的距离}//题目维护的信息必经过u的情况//x表示u和fa[u]之间的信息d[u]=x;//初始化为xtop=0;sort(st,st+top);//排序intres=0;for(intl=0,r=top-1;l<r;){//枚举l,r必单调减if(st[l]+st[r]<=k)res+=r-l,l++;}}vis[u]=1;//u算了p[i].w,两个分支在同一颗子sum=sz[v];//找子树v的重心前的初始化get(v,-1);//rt存了重心}ans=0;}head[a]=tot++;}intes[Maxn<<1];//欧拉intd[Maxn<<1];//深度}pw[0]=-1;pw[i]=i&i-1?pw[i-1]:pw[dp[i][j]=mymin(dp[i][j-1],dp[i+(}intrmq_ask(intl,intr){//查询l和r的LCAreturnes[mymin(dp[l][k],dp}voiddfs(intu,intfa,intsp){//sp表示深度es[++num]=u;//子树返回}}tot=num=0;}}/*****离线Tarjan*****//***复杂度O(n+q)***/head[a]=tot++;}ah[a]=tot1++;}}fa[u]=u;//自己指向自己,不这样的话,访问u和u的LCA就可能出错}vis[u]=1;//设置已访问for(inti=ah[u];i!=-1;i=ask[i].next){//处理与u关联的边if(vis[v])//若v已访问,则说明u,v的lca是v所在集合的指向ask[i].lca=ask[i^1].lca=}tot=tot1=0;}/*****非递归Tarjan*****/voidLCA(intx,intn){//n为节点数pre[x]=-1;}st[++top]=v;//入栈pre[v]=u;//记录父亲cur[u]=p[i].next;//修改cur}//u的所有孩子都已搜索完vis[u]=1;//设置u的访问标志for(inti=ah[u];i!=-1;i=ask[i].next){//处理与u关联的查询ask[i].lca=ask[i^1].lca=}top--;}}intf[Maxn][20];//f[i][j]表示i的2^j个父亲intdep[Maxn];//深度dep[u]=dep[fa]+1;//保证dep}//dep[0]=0;//全局变量已为0dfs(1,0);//父亲为0for(intj=0;j<18;j++)//更新至2^18=262144if(!f[i][j])f[i][j+1]=0;}if(dep[v]>dep[u])//保证v的深度小intdf=dep[u]-dep[v],t=0;t++;//倍增df>>=1;}for(inti=18;i>=0;i--)//二分逼近LCA}returnf[u][0];//最后逼近到LCA的儿子}1.1.6树链剖分head[a]=tot++;}}}}}intfa[Maxn];//父亲intson[Maxn];//重儿子intdep[Maxn];//深度voiddfs1(intu,intpre){//u-sz[u]=1;son[u]=0;//初始化为0dep[u]=dep[pre]+1;//必须保证dep[0]=0sz[u]+=sz[v];//更新sz[u]son[u]=v;//更新son[u]}//叶子节点不做for,因此son[u]=0}intdfn[Maxn];//时间戳if(v!=fa[u]&&v!=son[u])//搜索轻边dfs2(v,v);//可能成为重链的top端,父亲是自己}}tmpdfn=0;//sz[0]=dep[0]=0;//全部变量已为0}voidsolve(inta,intb,intw){//a,b为原先的idwhile(top[a]!=top[b]){//a,b在不同的重链上swap(a,b);//保证a重链顶端节点深度大a=fa[top[a]];//沿轻边}//a,b在同一条重链上if(dep[a]>dep[b])swap(a,b);//保证a的深度小(时间戳小)}voidbfs(intx){//维护好dep,sz,son,faq[0]=x,Top=1;for(inti=0;i<Top;i++){//维护好dep和fadep[v]=dep[u]+1;}for(inti=Top-1;i>=0;i--){//维护好sz和son}}voiddfs(intx){//维护好top和dfnq[0]=x,Top=1;vis[x]=1;vis[son[u]]=1;}Top--;}vis[v]=1;}}}tmpdfn=0;}1.2拓扑排序booltopu(intn){//点的编号1~n,调用前统计好inqt=0;}}}//主函数中初始化memset(adj,0x3f,sizeovoiddijkstra(intu,intn){//u为源点,n为顶点个数for(inti=1;i<=n;i++)//初始化vis[u]=1,dist[u]=0;for(inti=1;i<n;i++){//n-1趟添加点intminn=inf,v=0;vis[v]=1;//dist[v]+adj[v][j]不爆int}}1.3.2Bellman_ford//顶点编号从0开始，边的编号从0开始（邻接表版）voidbellman(intu,intn,intm){//u表示源点,n表示顶点数,m表示边数dist[u]=0;for(inti=1;i<n&&flag;i++){//n-1趟更新//dist[p[j].u]+p[j].w不爆int}}//顶点从1开始(邻接矩阵版)dist[u]=0,pre[u]=0;//源点dist[j]=dist[k]+adj[k][j],pre[j]=k;}shortest[tot++]=fr;shortest[tot++]=k;}1.3.3Spfa/*****复杂度O(kn),k平均为2******/inttot;p[tot].w=c;head[a]=tot++;}boolspfa(intu,intn){//n为顶点总数dist[u]=0,cnt[u]++;q[e=1]=u;vis[v]=0;intr=p[i].to,w=p[i].w;dist[r]=dist[v]+w;vis[r]=1;q[e=(e+1)%Maxn]=r;}}}tot=0;}/*****复杂度O(n^3)******///当i==j时,adj[i][j]=inf,最短路adj[i][j]=min(adj[i][j],adj[i][k]+//当i==j时,adj[i][j]=inf,最小值最大化adj[i][j]=max(adj[i][j],min(adj[i][k],a//当i==j时,adj[i][j]=0,集合运算//当i==j时,adj[i][j]=inf,最大值最小化adj[i][j]=min(adj[i][j],max(adj[i][k],a1.4最小生成树/*****复杂度O(n^2)******///加入生成树的点dist=-1intans=0;}}/*****复杂度O(eloge)*****/}voidinit(intn){//顶点编号从1开始}}}//存在最小生成树//不要忘了init()和sort()intkruskal(intn,inttot){//返回MST的权值之和}}}1.4.3次小生成树}intfa[Maxn],head[Maxn],ed[}}}maxcost[j][k]=maxcost[k][j]=p[i}}}{scanf("%d%d%d",&p[i]//枚举未在MST中的边,替换瓶颈边}}//先求MST,然后树形dp求瓶颈数组1.4.4生成树计数Kirchhoff矩阵:1.5.1图的深度优先遍历详解/*正向边分两种:反向边分两种:通过vis,dfn数组和fa可以区别4种边父亲)并且有等式:遍历所有边一遍:*/1.5.2割点(含连通分量的统计)/*树边:dfs树中的边*//*low[u]表示从u或者u的子孙出发通过回边可以到达的最小深度优先数low[u]=min(dfn[u],min(low[v]|v为u的孩子节点),)割点的充要条件:根节点,有大于1个孩子节点*/inttim;//时间戳intdfs(intu){//返回low(u)if(!dfn[v]){//u->v为树边if(lowv>=dfn[u])sub[u]++;}else//u->v为反向边}}voidinit(intn){//n为节点数tim=0;}1.5.3点双连通分量/***复杂度O(n+m)***/inttim;//时间戳/***使用dfs需保证图的点数大于1***/intdfs(intu,intfa){//返回low(u)piicur=make_pair(uif(!dfn[v]){//u->v为树边son++;if(lowv>=dfn[u]){//u为割点bcc[cnt].clear();//清空上组数据do{//得到编号为cnt的点双连通分量}}}}}}voidinit(intn){//n为节点数tim=cnt=0;}1.5.4割边(含多重边)/****前向星,根节点为1号点****/inthead[Maxn],vis[Maxn],d}vis[u]=1;}}}}1.5.5点连通度/*独立轨:设A,B为无向图的两个顶点,从A到B的2条没有公共内部顶点的路径,互称为独立轨,A到B独立轨的最大条数,记做P(A,B)∉E}*/1.5.6强连通分量/*****复杂度O(n+m)*****/intdfn[Maxn];//时间戳intlow[Maxn];//u和u的子孙能返回的最低深度intst[Maxn];//栈inttmpdfn;//时间戳,从1开始in[u]=1;if(!dfn[v]){//未访问}}scc++;in[st[top]]=0;}scc=0;}}/****非递归版本****/for(inti=1;i<=n;i+/n为节点总数}if(lx[v]!=-1)low[v]=min(low[v],if(nx[v]!=-1){//有儿子if(!dfn[p[nx[v]].to]){//树边}elseif(in[p[nx[v]].to])//回边}in[st[top]]=0;}}}/*****复杂度O(n+m)*****/inthd1[Maxn];//原图inthd2[Maxn];//逆图hd1[a]=tot++;hd2[b]=tot++;}inttop;//栈顶voiddfs1(intu){//求原图dfs后序遍历序列vis[u]=1;}}voiddfs2(intu){//对逆图按dfs后序递减搜索vis[u]=1;}}top=scc=0;scc++;}}head[u]=tot++;}//x=xvalory=yvaladdedge(x^1,y);//~x->yaddedge(y^1,x);//~y->x}//~(x=xvalandy=yval)==>x=~xvalory=~yval//即x=xval与y=yval矛盾}//x=xvalandy=yval==>(xorx)and(yory)}intdfn[Maxn];//时间戳intlow[Maxn];//u和u的子孙能返回的最低深度intst[Maxn];//栈inttmpdfn;//时间戳,从1开始in[u]=1;if(!dfn[v]){//未访问}}scc++;in[st[top]]=0;}scc=0;}}booljudge(intn){//n为变量个数for(inti=0;i<n;i++)//下标从0开始}1.5.8欧拉回路/***Hierholzer算法***//***复杂度O(n+m)***///这里用i来存正向边,i^1来存反向边tp=ap=0;tmp[tp++]=start;//选择起点}if(!flag){//u已经搜索完}}1.6.1基本概念增广路(可改进路):所有前向弧都是非饱和弧残留网络:原图中弧(c(u,v),f(u,v))对应残留网络中与其同向的流量为顶点的层次:在残留网络中,从源点到该顶点的最短路径长度(边的数目,不是指层次网络:对残留网络分层后,删去比汇点层次更高或者同层的顶点(保留汇点),并删去与这些顶点关联的弧,再删去从某层顶点指同层顶点和底层顶点的弧,其允许弧:在反向标号的残留网络中,边<u,v>满足d[u]=d[v]+1;在正向标号的层最大流最小割定理:网络流流量等于任意割净流量,割的净流量小于等于割的容量,因此网络流流量小于等于任意割的容量,等号成立当且仅当网络流流量达到限制条件:除源点、汇点外，其他点流量守恒(流入等于流出)1.6.2Edmonds_Karp/*****复杂度O(n*m^2)*****/intcap[Maxn][Maxn];//边容量intalpha[Maxn];//改进量intq[Maxn];//队列intm,n;//边,节点数memset(flow,0,sizeof}intmaxflow=0;memset(alpha,0,sizewhile(s<=e&&!alpha[t]){//bfs找增广路alpha[i]=min(alpha[u],cap[u][i]-f}}}}}1.6.3Dinic(递归+多路增广)}p[Maxn*Maxn*2];//完全图(反向边)乘2倍intq[Maxn];//BFS队列intd[Maxn];//层次inttot;//初始化0}}d[src]=0;d[v]=d[u]+1;}}}intdfs(intu,intalpha){//dfs返回值小于等于alphaintw,used=0;//used不可能大于alphafor(inti=head[u];i!=-1&&//当used=alpha,直接退出w=dfs(v,min(alpha-used,p[i].cap));//w<=alused+=w;//used<=al}}intdinic(){//不要忘记初始化tot和head数组intans=0;}/*****复杂度O(n^2*m)*****/}p[Maxn*Maxn*2];//完全图(反向边)乘2倍intq[Maxn];//BFS队列intd[Maxn];//层次inttot;//初始化0}}d[src]=0;d[v]=d[u]+1;}}}intdfs(intu,intalpha){//dfs返回值小于等于alphaintw,used=0;//used不可能大于alphafor(inti=cur[u];i!=-1&&//当used=alpha,直接退出w=dfs(v,min(alpha-used,p[i].cap));//w<=alused+=w;//used<=al}}if(!used)d[u]=-1;}intdinic(){//不要忘记初始化tot和head数组intans=0;for(inti=src;i<=t;i++)}}1.6.4Isap(递归+多路增广)/*****Isap(递归+gap优化+无BFS)*****//*****复杂度O(n^2*m)*****/intd[Maxn];//层次intgap[Maxn];//gap[x]为d[]=x出现的个数inttot;//初始化为0}}intdfs(intu,intalpha){//dfs返回值小于等于alphaintw,used=0;//used不可能大于alphaintmind=n-1;//最低层次,使用nfor(inti=head[u];i!=-1&&used<alpha//当used=alpha,直接退出,使用nw=dfs(v,min(alpha-used,p[i].cap));//w<=alused+=w;//used<=al}}}if(--gap[d[u]]==0)d[src]=n;//出现断层,使用ngap[d[u]=mind+1]++;}}intres=0;gap[0]=n;//使用nwhile(d[src]<n)//使用n}/*****Isap(递归+gap优化+cur优化+BFS初始化)*****//*****复杂度O(n^2*m)*****/intd[Maxn];//层次intq[Maxn];//队列intcur[Maxn];//当前弧intgap[Maxn];//gap[x]为d[]=x出现的个数inttot;//初始化为0}}gap[d[t]=0]=1;//汇点为0层gap[d[v]=d[u]+1]++;}}}intdfs(intu,intalpha){//dfs返回值小于等于alphaintw,used=0;//used不可能大于alphafor(inti=cur[u];i!=-1&&used<alpha//当used=alpha,直接退出,使用nw=dfs(v,min(alpha-used,p[i].cap));//w<=alused+=w;//used<=al}}intmind=n-1;//最低层次,使用n}if(--gap[d[u]]==0)d[src]=n;//出现断层,使用ngap[d[u]=mind+1]++;}}intres=0;while(d[src]<n)//使用n}1.6.5Push_relabel/*****复杂度O(n^2*m)*****/intcap[Maxn][Maxn];//残intn;//点的个数n=x;//须修改}intmaxflow=0;d[src]=n;//源点高度为n}elsemind=min(mind,d[}}}}intcap[Maxn][Maxn];//残intn;//点的个数n=x;//须修改}intmaxflow=0;d[src]=n;//源点高度为n//queue<int>q;priority_queue<List>q;//优先队列}elsemind=min(mind,d[v]);//不可推}d[u]=mind+1;}}}1.6.7最小割//vis[]=1为S集合的元素,vis[]=0为T集合的元素vis[u]=1;}01规划：h n2的无向边变成两条容量为边权w的有向边，源点到每个点连边边，容量为U=2Σp+Σw，每个点向汇点连边，对于点v，容量为v−2pv,dv为Σwe，pv为点v的权值，g为二分值，那么盖Σ[B(i,u)+g(i,u)]=Σ[B(u,j)+g(u,j)](i,u)∈E(u,j)∈E⇋ΣB(i,u)-ΣB(u,j)=Σg(u,j)-Σg(i,u)(i,u)∈E(u,j)∈E(u,j)∈E(i,u)∈EΣB(i,u)-ΣB(u,j),(i,u)∈E(u,j)∈E考虑在自由流组成的网络中求得可行流,然后累加上每条边的下界来得到可行流,但这样无法保证每个点的流量平衡。于是需要加入附加出去的多,所以由附加源向u连一条容量为M入的多,所以由点u向附加汇连一条容量为-M[u]的边,保证点u多流然后保留原图的边,容量改为自由流,这样在有附加源汇的新图能够达的可行流同时使得源汇也满足流量平衡的条件,于是采用无源汇上下方法一:按有源汇上下界可行流方法判断可行流是否存在,若存在则对原图的源点和汇点做一遍最大流,扩大之前的可行流,每条边的实际流量,而是要多减去一个inf,因为第一遍判断可行流时,加了一条汇点第二遍求最大流时,第一次被增广的流量又回到汇点,因此源点通过这取决于是否删除附加源和附加汇,若删除了则需加上下界,否则因为源点连出的下界和已记录在源点连向附加汇的边上,并且在第一遍判可行流时已被增广,所以无需再加(是否在做第二遍最大流前删除附加源和附加汇以及它们的所有连边并不影响第二遍的增广,因为不存在从源点经过这些边到汇点的增广路,只是如果不删除的话,源点和汇点(包括那些下界出入不平衡的中间点)的相邻边会增加,也就是上面讨点到源点的这条边,也并没有大的影响,因为这条边必然会被增广完,方法二:二分汇点连向源点这条边的下界,然后判断无源汇上下界网络流是否存在可行流,因为若二分下界小于等于最大流等价于存在可方法一:与最大流类似,先判断可行流是否存在。若存在,则以原图的汇点作为源点,以原图的源点作为汇点,边不改变,做一遍反向最大流,实际对原图来说是在不断地减少可行流,当反向达到最大,则正向刚好流,同样注意如果删掉附加源和附加汇以及它们的所有连边,那么最小流还需要加上源点连出去边的下界,并且由于是方向增广,因此汇点连向源点的边增广完全,因此对源点来说这条边的反向边刚好为0,所以方法二:二分汇点连向源点这条边的上界,然后判断无源汇上下界网络流是否存在可行流,因为若二分上界大于等于最小流等价于存在可方法三:和判断有源汇上下界可行流一样建图,但是需要分两个阶段,第一阶段是不需要加汇点连向源点的边(下界为0,一遍附加源到附加汇的最大流;第二阶段是加上汇点连向源点的边,然后再跑一遍附加源到附加汇的最大流,如果满流,那么最小流刚好为汇点连向源点的这条边的流量,否则不存在可行流。可以这么理解,只要最后补齐的图一样,分阶段增广与一步增广最后达到的效果是一样的,因此判断是否存在可行流依然成立。我们可以考虑下为什么要加汇点到源点的这条边,本质是因为源汇不满足流量平衡的条件,因此加入附加源和附加汇建立的图除源汇点外,在增广自由流后得到的伪流和下界叠加后刚好得到可行流,但这样的前提是强制考虑自由流可以流动,实际因为汇点并不平衡,因此这些被强制考虑流动的自由流应囤积在汇点,然而真正在增广的图的汇点是附加汇,因此不会有流囤积在原图的汇点,也就是自由流并不会流动,那么我们强制在汇点到源点连流向源点,并且这样做刚好使得源汇也流量平衡,成为无源汇网络。那么要得到最小流,我们的想法是尽量使得囤积在汇点的流量减少,因此,第一阶段不加这条边,是想借用网络本身的结构让附加源的流量尽量流向附加汇,这种情况会出现是原图中存在回路(也就是电路当中的短路情况),这样便能尽量增广一部分,而剩余的一部分只能通过第二阶段来增广了,于是如果原图中不存在短路情况,那么可以省去第一阶段,head[u]=tot++;}}vis[u]=0;vis[v]=1;}}//returndist[t]<0;//最小费用流可行流}intalpha=inf,ans=0;alpha=min(alpha,p[i].cap);//可改进量for(inti=from[t];i!=-1;i=from[p[i].from]){//增广}}intans=0;}1.7.1基本概念/*支配与支配集:设无向图G(V,E),V∗为V的子集,对于∀v∈(V−V∗),∃U∈V∗,使得(u,v)∈E,称u支配v，并称V∗为G的一个点支配集(简称支配集)点覆盖集:设无向图G(V,E),V∗为V的子集,若对于∀e∈E,∃v∈V∗,使得v与e相关联,则称v覆盖e,并称V∗为G的一个点覆盖集(简称点覆盖)点独立集:设无向图G(V,E),V∗为V的子集,若V∗中任何两个顶点均不相邻,则称V∗为G的点独立集(简称独立集)团:设无向图G(V,E),V∗为V的子集,且V∗是完全图覆盖与边覆盖集:设无向图G(V,E),E∗为E的子集，若与e相关联,则称e覆盖v,并称E∗为边覆盖集(简称边覆盖)配盖点与未盖点:设v是图G的一个顶点,如果v与匹配M中的某条边关联,则称v是M的盖点(M饱和点);如果v不与任意一条属于匹配M的边相关联,则称v是匹配M的未盖点(非M饱和点)的定义矛盾;大点独立集了→{α0+β0=n,n为顶点数}定理5:在无向图G中,V∗是G的团,当且仅当V∗是G的补图的独立集推论:在无向图G中,V∗是G的极大(最大)团,当且仅当V∗是G的补图的极大(最定理6:设无向图G的顶点个数为n,且G中无孤立点⑴设M为G的一个最大匹配,对于G中M的每个未盖点v,选取一条与v关联的边所组成的集合为N,则W=M∪N为G中的最小边覆盖⑵设W为G的最小边覆盖,若G中存在相邻的边就移去其中的一条,设移去的边集为N,则M=W-N为G中一个最大匹配⑶G中边覆盖数α1与匹配数β1,满足α1+β1=n其他性质:公式:α0+β0=n无孤立点有X部未做标记的点和Y部做好标记的点组成了最小点覆盖集将所有的点拆成两个点,V拆成Vx和Vy,原图中有边A->B,新图中添加图合并两条路径.并且由于是匹配,X部的每个点最多连出去一条边到Y部,对应原图这些点的出度至多为1,同理Y部的每个点最多来自X部一条边,对应原图每适用有向无环图*/1.7.2最大团intcq[Maxn];//当前最大团序列,下标从0开始intclique[Maxn];//最终最大团序列,下标从0开始intans;//最大团数if(tot>ans){//每次增加1个点,最大团数最多增加1//需要序列}if(adj[u][v]){//取点vif(!adj[cq[w]][v]){//点v与已有最大团不相容}}}}ans=0;cq[0]=i;//选择点icnt[i]=ans;//更新cnt}}/*****复杂度O(n^3)*****/intadj[Maxn][Maxn];//邻intmatch[Maxn];//match[i]表示y组i与x组match[i]匹配intdeep;//优化vis数组for(intv=1;v<=y;v++){//扫描y组,下标[1,y]}}}intans=0;for(inti=1;i<=x;i++){//扫描x组,[1,x]}}/*****复杂度O(n^3)*****/intadj[Maxn][Maxn];//邻intmx[Maxn];//X匹配Yintmy[Maxn];//Y匹配Xintq[Maxn];//BFS队列intpre[Maxn];//记录Y指向的Xwhile(1){//回溯修改}}pre[v]=u;}}}intans=0;for(inti=1;i<=x;i++)//扫描x组,[1,x]if(bfs(i))ans++;}1.7.5二分图(Hopcroft_Karp)/*****复杂度O(n^2.5)*****/intadj[Maxn][Maxn];//邻intdx[Maxn],dy[Maxn];//X/Y的层次intmx[Maxn],my[Maxn];//X/Y匹配Y/Xintq[Maxn];//BFS队列intdeep;//优化vis数组for(inti=1;i<=x;i++)//扫描X组}for(intv=1;v<=y;v++){//扫描Y组dy[v]=dx[u]+1;//更新距离else{//从my[v]继续往下增广}}}for(intv=1;v<=y;v++){//扫描Y组}}}intans=0;deep=0;if(mx[i]==-1){//未盖点deep++;}}}1.7.6完全二分图的最大匹配(KM)/***复杂度O(n^3)***/intadj[Maxn][Maxn];//邻intmatch[Maxn];//match[i]表示X组i与Y组match[i]匹配intlx[Maxn],ly[Maxn];//X和Y部的标号,辅助作用intvx[Maxn],vy[Maxn];//X和Y部的点是否被访问intmn[Maxn];//mn[i]表示y组i与交错路上的X组点边权最小值intx,y;//X和Y部的点数intdep;//优化vx和vy数组vx[u]=dep;for(intv=1;v<=y;v++){//扫描y组,下标[1,y]mn[v]=min(mn[v],lx[u]+ly[v]-adj[u][vmatch[v]=u;}}}intKM(){//保证x<=ydep=0;lx[i]=-inf;}for(inti=1;i<=y;i++)ly[i]=0;for(inti=1;i<=x;i++){//扫描x组,[1,x]for(intj=1;j<=y;j++)mn[j]=inf;dep++;//for(intj=1;j<=x;j++)mn[j]=inf;if(vx[j]==dep)lx[j]-=d;elsemn[j]-=d;}intans=0;//for(inti=1;i<=x;i++)ans+=lx[i];//for(inti=1;i<=y;i++)ans+=ly[i];returnans=-inf;}}//adj的值回赋值给lx,可能在后面会减小//INF不能太小,以防爆intx=n,y=m;//不要忘记给x,y赋值,x<=yadj[i][j]=INF;}1.8.1基本概念/*K5(5阶完全图),K3,3(完全二部点和边的范围区域的边界)区域i与区域j有公共边,则连接这两个区域对应的点,若原平面图有桥(性质:定理4:设G为n(n>=3)阶简单连通的平面图,G为极大平面图当且仅当G的每个区域度数为3定理5:设G*是连通平面图G的对偶图,n*,m*,r*和n,m,r分别为G*和G的顶点数、⑷设顶点vEQ\*jc3\*hps17\o\al(\s\up4(*),i)位于G的区域Ri,则deg(vEQ\*jc3\*hps17\o\al(\s\up4(*),i))=deg(Ri),即对偶图中顶点vEQ\*jc3\*hps17\o\al(\s\up4(*),i)的度数等定理6:如果G是一个阶n>=3,边数为m的平面图,则m<=3n-6推论1:如果G是一个阶n>=3,边数为m>3n-6的图,则图G是非平面图推论2:每个平面图都含有一个小于等于5的顶点推论3:5阶完全图是非平面图和(或)去掉度数为2的顶点后,使得G1和G2同构,则称G1和G2是在2度顶点内同构的在2度结点内同构的子图收缩:设e是图G的一条边,从G中删去e并将e的两个顶点合并,删除由此得到图G2同构的图,则称G1可以收缩到G2.注意,收缩边e并不要求e的两个顶点度数为2Wagner定理:图G是平面图,当且仅当G中既没有可收缩到K5的子图,也没有可以收缩到K3,3的子图欧拉公式:如果G是一个顶点数为n,边数为m,面数为r的连通平面图,则有恒等式:n-m+r=2*/1.9.1基本概念/*顶点颜色均不同色数(Χ(G)):如果能用k种颜色对图G进行顶点着色,就称对图G进行了k着色,也称G是k-可着色的.若G是k-可着色的,但不是(k-1)-可着色的,称G是k色的图,并称这样的k为图G的色数定理1:Χ(G)=1当且仅当G是零图(没有边的图)定理2:n阶完全图的色数为n定理3:奇圈的色数为3定理4:图G的色数为2当且仅当G是一个非空的二部图边色数(Χ1(G)):如果能用k种颜色对图G进行边着色,就称对图G进行了k边着色,也称G是k-边可着色的.若G是k-边可着色的,但不是(k-1)-边可着色的,称G是k边色的图,并称这样的k为图G的边色数定理1:设图G为长度大于或等于2的偶圈,则Χ1(G)=Δ(G)=2;设图G为长度大于或等于3的奇圈,则Χ1(G)=Δ(G)+1=3面色数(Χ*(G)):如果能用k种颜色给平面图G进行面着色,则称G是k-面可着色定理1:平面图G是k-面可着色的,当且仅当它的对偶图G*是k色的图*/1.9.2顺序染色(不一定是最优解)/*****复杂度O(n^2)*****/intcolor[Maxn];//color[i]表示点i染的颜色intans=-1;//需要染色最大标号,从0开始memset(color,-1,sizefor(intj=0;j<n;j++)//标记点i的邻接点染过的颜色color[i]=j;//给点i染色ans=max(ans,j);//更新答案}}/*****复杂度O(n^2)*****/intcolor[Maxn];//color[i]表示点i染的颜色intans=-1;//需要染色最大标号,从0开始memset(color,-1,sizefor(intj=0;j<n;j++)//标记点i的邻接点染过的颜色color[i]=j;//给点i染色ans=max(ans,j);//更新答案}}1.9.3平面图暴力染色(最优解)/*****复杂度O(3^n)*****/intcolor[Maxn];//color[i]表示点i染的颜色intn;//顶点数boolcheck(intu,intc){//判断u是否可以染成颜色cif(adj[u][v]&&color[v]==c)//冲突}voiddfs(intd){//最多只染3种颜色//当color中的最大元素最小时,染色连续ans=min(ans,*max_element(color}}//在主函数里加memset(adj,0,sizeofadj)//调用solve前构造好邻接矩阵color[0]=1;//点0染成颜色1dfs(1);//从点1开始染色}/*****复杂度O(E)*****/intto,next,w;inttot;intc[Maxn];//染色1,2head[a]=tot++;}c[1]=1;//染色第一个点要在dfs外初始化booldfs(intu){//dfs黑白染色intv=p[i].to;}}}2.1.1块状数组inta[Maxn];//存元素voidmaintain(intx){//维护x所在的块intlb=x/sz*sz,rb=min(n,lb+sz)-1;//[lb,}voidinit(){//初始化}voidmodify(intx,inty){//修改a[x]=y}if(x_sz==y_sz){//同一块}else{//不同块for(inti=x_sz+1;i<y_sz;i++)for(inti=y_sz*sz;i<}}/***复杂度sqrt(n)***///块x对应的区间[x*sz,(x+1)*sz-1]inta[Maxn];//原数组inttag[Maxn];//标记intpos[Maxn];//pos[i]表示i所在的块号voidmaintain(intx){//维护块x的性质intl=x*sz,r=min(n,l+sz);//[l,r)}sz=(int)sqrt(n);//块大小为sqrt(n)m=(n+sz-1)/sz;//n/sz向上取整//a,b,tag数组初始化for(inti=0;i<m;i++)tag[i]=0;}voidupdate(intx,inty,intv){//区间[x,y]加上v}//x,y所在块暴力for(inti=pos[x]+1;}}//区间[x,y]大于等于v的个数统计intans=0;}//x,y所在块内暴力统计ans+=b+(i+1)*sz-lower_bound(b+i*sz,b+(i+1)*sz}}2.1.2块状链表blocklist():sz(0),nexvoidrefresh(){//对该块sum更新sum=0;}}*head=NULL;//x必须传引用,使x变成该块的个数blocklist*get_pos(int&x){//获得第x个元素在ret块的位置}}boolmerge(blocklist*pos){//合并pos和pos->nextmemmove(pos->num+pos->sz,pos->next->num,sizeof(int)}}}//一般先调用get_pos,使x变成该块的个数voidsplit(blocklist*pos,intx){//分裂成x-1和sz-x+1blocklist*tmp=pos-memmove(pos->next->num,pos->num+x-1,sizeof(int)//先更新sz,再refreshpos->next->sz=pos->sz-x+1;pos->next->refpos->sz=x-1;pos->ref}//x>=1,若x大于块表元素总数,插在表尾voidinsert(intx,intn){//将n个元素插入到x所在的位置,x后挪blocklist*pos=get_pif(!head)head=pos;//空表插入else{//x大于块表元素总个数blocklist*it;//表尾插入}blocklist*tmp=pos-}scanf("%d",&pos->num[pos->sz++]);//读入方式}maintain();//维护链表}voidremove(intx,intn){//删除x后(包括x)的n个元素,删除区间[x-1,y-1]/*intsum=0,y=x+n-1;for(blocklist*it=head;it;it=it->next)sum+=it->sz;if(x>sum)return;y=min(y,sum);n=y-x+1;*/inty=x+n-1;blocklist*x_pos=get_pos(x),*y_pos=get_pif(x_pos==y_pos){//同一块memmove(x_pos->num+x-1,y_pos->num+y,sizeof(int}for(blocklist*it=x_pos->next;it!}}intget_sum(intx,intn){//获得x后（包括x）n个数的和inty=x+n-1,ret=0;blocklist*x_pos=get_pos(x),*y_pos=get_p}else{//不同块for(inti=x-1;i<x_pos->sz;i++)//x所在块for(blocklist*it=x_pos->next;it!ret+=it->sum;//按块计算for(inti=0;i<y;i++)//y所在块}}voidremove_blocklist(bl}intcnt=0;for(blocklist*it=heprintf("block%d:",printf("sum:%d\n",}}//bitmap[i]的第j位表示32*i+j}}bitmap[x>>5]&=~(1<<(x}/*****复杂度O(n*α(n))*****/}intfindset(intx){//递归版}while(x!=r){i=fa[x];fa[}voidunionset(intx,inty){//rank[y]++;}}}}voidunionset(intx,i}voiddel(intx){//删除x就是更改x的时间戳}intfa;//父亲intdep;//深度}intrt[Maxn];//根}}//返回以数组下标k为根的子树中pos的下标intmid=l+r>>1;}//只需复制一份从根(数组下标为k)到叶子u的一条路径//修改tr[t].fa=vif(l==r){//找到u,对应新的节点ttr[t]=PUFD(v);//修改父亲指向v}intmid=l+r>>1;}//返回以数组下标k为根的子树中pos的父亲下标}//修改以数组下标k为根的子树中pos对应的深度if(l==r){//找到pos对应节点,深度+1}intmid=l+r>>1;}voidinit(intn){//初始化第0次操作,fa[i]=isz=0;}voidunionset(inti,intu,intv){//第i次操作if(tr[p].dep>tr[q].dep)swap(p,q);//p深度小update(rt[i-1],1,n,rt[i],tr[p].fa,tr[q].fif(tr[p].dep==tr[q].}voidprint(intk){//中序遍历printf("%d%d%d%d%d\n",k,tr[k].l,tr[k].r,tr[k].fa,tprint(tr[k].l);}2.4DancingLinksX算法/*选中k行,若k行有元素i,j,则覆盖i,j的其他行均*/#defineMaxr970//行数#defineMaxc370//列数/***DancingLinksX算法***/intL[Maxn],R[Maxn],U[Maxn],D[Mvoidinit(intm){//m为列数L[i]=i-1,R[i]=i+1,U[i]}voidlink(intr,intc){//插入r行c列为1的元素row[sz]=r,col[sz]=c,s[c]++;U[D[sz]]=D[U[sz]]=sz;R[sz]=R[fst[r]],L[sz]L[R[sz]]=R[L[sz]]=s}/*并未删除c列,只是在辅助元素将c删除,*/voiddel(intc){//删除c列D[U[j]]=D[j],U[D[j]]=U[j],s[col[j]]--;}/**/voidrec(intc){//恢复c列D[U[j]]=U[D[j]]=j,s[col[j}/*调用dance(0),返回true,表示存在解*/}for(inti=D[c];i!=c;i=D[i]){//枚举选中行row[i]st[dep]=row[i];//记录for(intj=R[i];j!=i;j=R[j])//}}/*****堆*****//***建堆O(n),单次访问O(logn)***/heap[p]=heap[q];p=q;}}heap[p]=heap[q];p=q;}}}intgetmin(){//取堆顶}}voidbulid(){//数组建堆}priority_queue<int>h,d;//h存所有元素,d存删除的元素voidadd(intx){//插入xvoiddel(intx){//删除xvoidfix(){//将已删除的元素弹出hwhile(d.size()&&h.top()==d}intfirst(){//堆顶}voidpop(){//弹出堆顶}2.6树形结构2.6.1树状数组//x从1开始