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點(diǎn)、線段、 140 140 141 141 143 143 143 144 146 147 1484.1整數(shù)的因子分解 148 1484.1.2Prollard 149 1504.2乘法逆元 151 152 152 153 153 153 155 158 158 158 159 159 1604.6一些重要積性函數(shù) 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[]記錄直徑上各點(diǎn)到da的路徑長度da=1;db=1;top=0;while(db!=da){st[top++]=db;db=//將st反轉(zhuǎn)過來for(inti=0;i<(top-1)/2;i++)//搜側(cè)鏈intl=0,r=dist[st[top-1]];//r直徑的長度//l側(cè)鏈的最大長度1.1.4樹的點(diǎn)分治intbal[Maxn];//節(jié)點(diǎn)最多的子樹intk;//統(tǒng)計(jì)樹上距離小于k的點(diǎn)對}bal[u]=max(bal[u],sum-s}voiddfs(intu,intfa){//計(jì)算以u為根的子樹節(jié)點(diǎn)到u的距離}//題目維護(hù)的信息必經(jīng)過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必單調(diào)減if(st[l]+st[r]<=k)res+=r-l,l++;}}vis[u]=1;//u算了p[i].w,兩個(gè)分支在同一顆子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*****//***復(fù)雜度O(n+q)***/head[a]=tot++;}ah[a]=tot1++;}}fa[u]=u;//自己指向自己,不這樣的話,訪問u和u的LCA就可能出錯(cuò)}vis[u]=1;//設(shè)置已訪問for(inti=ah[u];i!=-1;i=ask[i].next){//處理與u關(guān)聯(lián)的邊if(vis[v])//若v已訪問,則說明u,v的lca是v所在集合的指向ask[i].lca=ask[i^1].lca=}tot=tot1=0;}/*****非遞歸Tarjan*****/voidLCA(intx,intn){//n為節(jié)點(diǎn)數(shù)pre[x]=-1;}st[++top]=v;//入棧pre[v]=u;//記錄父親cur[u]=p[i].next;//修改cur}//u的所有孩子都已搜索完vis[u]=1;//設(shè)置u的訪問標(biāo)志for(inti=ah[u];i!=-1;i=ask[i].next){//處理與u關(guān)聯(lián)的查詢ask[i].lca=ask[i^1].lca=}top--;}}intf[Maxn][20];//f[i][j]表示i的2^j個(gè)父親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]}//葉子節(jié)點(diǎn)不做for,因此son[u]=0}intdfn[Maxn];//時(shí)間戳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重鏈頂端節(jié)點(diǎn)深度大a=fa[top[a]];//沿輕邊}//a,b在同一條重鏈上if(dep[a]>dep[b])swap(a,b);//保證a的深度小(時(shí)間戳小)}voidbfs(intx){//維護(hù)好dep,sz,son,faq[0]=x,Top=1;for(inti=0;i<Top;i++){//維護(hù)好dep和fadep[v]=dep[u]+1;}for(inti=Top-1;i>=0;i--){//維護(hù)好sz和son}}voiddfs(intx){//維護(hù)好top和dfnq[0]=x,Top=1;vis[x]=1;vis[son[u]]=1;}Top--;}vis[v]=1;}}}tmpdfn=0;}1.2拓?fù)渑判騜ooltopu(intn){//點(diǎn)的編號(hào)1~n,調(diào)用前統(tǒng)計(jì)好inqt=0;}}}//主函數(shù)中初始化memset(adj,0x3f,sizeovoiddijkstra(intu,intn){//u為源點(diǎn),n為頂點(diǎn)個(gè)數(shù)for(inti=1;i<=n;i++)//初始化vis[u]=1,dist[u]=0;for(inti=1;i<n;i++){//n-1趟添加點(diǎn)intminn=inf,v=0;vis[v]=1;//dist[v]+adj[v][j]不爆int}}1.3.2Bellman_ford//頂點(diǎn)編號(hào)從0開始，邊的編號(hào)從0開始（鄰接表版）voidbellman(intu,intn,intm){//u表示源點(diǎn),n表示頂點(diǎn)數(shù),m表示邊數(shù)dist[u]=0;for(inti=1;i<n&&flag;i++){//n-1趟更新//dist[p[j].u]+p[j].w不爆int}}//頂點(diǎn)從1開始(鄰接矩陣版)dist[u]=0,pre[u]=0;//源點(diǎn)dist[j]=dist[k]+adj[k][j],pre[j]=k;}shortest[tot++]=fr;shortest[tot++]=k;}1.3.3Spfa/*****復(fù)雜度O(kn),k平均為2******/inttot;p[tot].w=c;head[a]=tot++;}boolspfa(intu,intn){//n為頂點(diǎn)總數(shù)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;}/*****復(fù)雜度O(n^3)******///當(dāng)i==j時(shí),adj[i][j]=inf,最短路adj[i][j]=min(adj[i][j],adj[i][k]+//當(dāng)i==j時(shí),adj[i][j]=inf,最小值最大化adj[i][j]=max(adj[i][j],min(adj[i][k],a//當(dāng)i==j時(shí),adj[i][j]=0,集合運(yùn)算//當(dāng)i==j時(shí),adj[i][j]=inf,最大值最小化adj[i][j]=min(adj[i][j],max(adj[i][k],a1.4最小生成樹/*****復(fù)雜度O(n^2)******///加入生成樹的點(diǎn)dist=-1intans=0;}}/*****復(fù)雜度O(eloge)*****/}voidinit(intn){//頂點(diǎn)編號(hào)從1開始}}}//存在最小生成樹//不要忘了init()和sort()intkruskal(intn,inttot){//返回MST的權(quán)值之和}}}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求瓶頸數(shù)組1.4.4生成樹計(jì)數(shù)Kirchhoff矩陣:1.5.1圖的深度優(yōu)先遍歷詳解/*正向邊分兩種:反向邊分兩種:通過vis,dfn數(shù)組和fa可以區(qū)別4種邊父親)并且有等式:遍歷所有邊一遍:*/1.5.2割點(diǎn)(含連通分量的統(tǒng)計(jì))/*樹邊:dfs樹中的邊*//*low[u]表示從u或者u的子孫出發(fā)通過回邊可以到達(dá)的最小深度優(yōu)先數(shù)low[u]=min(dfn[u],min(low[v]|v為u的孩子節(jié)點(diǎn)),)割點(diǎn)的充要條件:根節(jié)點(diǎn),有大于1個(gè)孩子節(jié)點(diǎn)*/inttim;//時(shí)間戳intdfs(intu){//返回low(u)if(!dfn[v]){//u->v為樹邊if(lowv>=dfn[u])sub[u]++;}else//u->v為反向邊}}voidinit(intn){//n為節(jié)點(diǎn)數(shù)tim=0;}1.5.3點(diǎn)雙連通分量/***復(fù)雜度O(n+m)***/inttim;//時(shí)間戳/***使用dfs需保證圖的點(diǎn)數(shù)大于1***/intdfs(intu,intfa){//返回low(u)piicur=make_pair(uif(!dfn[v]){//u->v為樹邊son++;if(lowv>=dfn[u]){//u為割點(diǎn)bcc[cnt].clear();//清空上組數(shù)據(jù)do{//得到編號(hào)為cnt的點(diǎn)雙連通分量}}}}}}voidinit(intn){//n為節(jié)點(diǎn)數(shù)tim=cnt=0;}1.5.4割邊(含多重邊)/****前向星,根節(jié)點(diǎn)為1號(hào)點(diǎn)****/inthead[Maxn],vis[Maxn],d}vis[u]=1;}}}}1.5.5點(diǎn)連通度/*獨(dú)立軌:設(shè)A,B為無向圖的兩個(gè)頂點(diǎn),從A到B的2條沒有公共內(nèi)部頂點(diǎn)的路徑,互稱為獨(dú)立軌,A到B獨(dú)立軌的最大條數(shù),記做P(A,B)?E}*/1.5.6強(qiáng)連通分量/*****復(fù)雜度O(n+m)*****/intdfn[Maxn];//時(shí)間戳intlow[Maxn];//u和u的子孫能返回的最低深度intst[Maxn];//棧inttmpdfn;//時(shí)間戳,從1開始in[u]=1;if(!dfn[v]){//未訪問}}scc++;in[st[top]]=0;}scc=0;}}/****非遞歸版本****/for(inti=1;i<=n;i+/n為節(jié)點(diǎn)總數(shù)}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;}}}/*****復(fù)雜度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];//時(shí)間戳intlow[Maxn];//u和u的子孫能返回的最低深度intst[Maxn];//棧inttmpdfn;//時(shí)間戳,從1開始in[u]=1;if(!dfn[v]){//未訪問}}scc++;in[st[top]]=0;}scc=0;}}booljudge(intn){//n為變量個(gè)數(shù)for(inti=0;i<n;i++)//下標(biāo)從0開始}1.5.8歐拉回路/***Hierholzer算法***//***復(fù)雜度O(n+m)***///這里用i來存正向邊,i^1來存反向邊tp=ap=0;tmp[tp++]=start;//選擇起點(diǎn)}if(!flag){//u已經(jīng)搜索完}}1.6.1基本概念增廣路(可改進(jìn)路):所有前向弧都是非飽和弧殘留網(wǎng)絡(luò):原圖中弧(c(u,v),f(u,v))對應(yīng)殘留網(wǎng)絡(luò)中與其同向的流量為頂點(diǎn)的層次:在殘留網(wǎng)絡(luò)中,從源點(diǎn)到該頂點(diǎn)的最短路徑長度(邊的數(shù)目,不是指層次網(wǎng)絡(luò):對殘留網(wǎng)絡(luò)分層后,刪去比匯點(diǎn)層次更高或者同層的頂點(diǎn)(保留匯點(diǎn)),并刪去與這些頂點(diǎn)關(guān)聯(lián)的弧,再刪去從某層頂點(diǎn)指同層頂點(diǎn)和底層頂點(diǎn)的弧,其允許弧:在反向標(biāo)號(hào)的殘留網(wǎng)絡(luò)中,邊<u,v>滿足d[u]=d[v]+1;在正向標(biāo)號(hào)的層最大流最小割定理:網(wǎng)絡(luò)流流量等于任意割凈流量,割的凈流量小于等于割的容量,因此網(wǎng)絡(luò)流流量小于等于任意割的容量,等號(hào)成立當(dāng)且僅當(dāng)網(wǎng)絡(luò)流流量達(dá)到限制條件:除源點(diǎn)、匯點(diǎn)外，其他點(diǎn)流量守恒(流入等于流出)1.6.2Edmonds_Karp/*****復(fù)雜度O(n*m^2)*****/intcap[Maxn][Maxn];//邊容量intalpha[Maxn];//改進(jìn)量intq[Maxn];//隊(duì)列intm,n;//邊,節(jié)點(diǎn)數(shù)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隊(duì)列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&&//當(dāng)used=alpha,直接退出w=dfs(v,min(alpha-used,p[i].cap));//w<=alused+=w;//used<=al}}intdinic(){//不要忘記初始化tot和head數(shù)組intans=0;}/*****復(fù)雜度O(n^2*m)*****/}p[Maxn*Maxn*2];//完全圖(反向邊)乘2倍intq[Maxn];//BFS隊(duì)列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&&//當(dāng)used=alpha,直接退出w=dfs(v,min(alpha-used,p[i].cap));//w<=alused+=w;//used<=al}}if(!used)d[u]=-1;}intdinic(){//不要忘記初始化tot和head數(shù)組intans=0;for(inti=src;i<=t;i++)}}1.6.4Isap(遞歸+多路增廣)/*****Isap(遞歸+gap優(yōu)化+無BFS)*****//*****復(fù)雜度O(n^2*m)*****/intd[Maxn];//層次intgap[Maxn];//gap[x]為d[]=x出現(xiàn)的個(gè)數(shù)inttot;//初始化為0}}intdfs(intu,intalpha){//dfs返回值小于等于alphaintw,used=0;//used不可能大于alphaintmind=n-1;//最低層次,使用nfor(inti=head[u];i!=-1&&used<alpha//當(dāng)used=alpha,直接退出,使用nw=dfs(v,min(alpha-used,p[i].cap));//w<=alused+=w;//used<=al}}}if(--gap[d[u]]==0)d[src]=n;//出現(xiàn)斷層,使用ngap[d[u]=mind+1]++;}}intres=0;gap[0]=n;//使用nwhile(d[src]<n)//使用n}/*****Isap(遞歸+gap優(yōu)化+cur優(yōu)化+BFS初始化)*****//*****復(fù)雜度O(n^2*m)*****/intd[Maxn];//層次intq[Maxn];//隊(duì)列intcur[Maxn];//當(dāng)前弧intgap[Maxn];//gap[x]為d[]=x出現(xiàn)的個(gè)數(shù)inttot;//初始化為0}}gap[d[t]=0]=1;//匯點(diǎn)為0層gap[d[v]=d[u]+1]++;}}}intdfs(intu,intalpha){//dfs返回值小于等于alphaintw,used=0;//used不可能大于alphafor(inti=cur[u];i!=-1&&used<alpha//當(dāng)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;//出現(xiàn)斷層,使用ngap[d[u]=mind+1]++;}}intres=0;while(d[src]<n)//使用n}1.6.5Push_relabel/*****復(fù)雜度O(n^2*m)*****/intcap[Maxn][Maxn];//殘intn;//點(diǎn)的個(gè)數(shù)n=x;//須修改}intmaxflow=0;d[src]=n;//源點(diǎn)高度為n}elsemind=min(mind,d[}}}}intcap[Maxn][Maxn];//殘intn;//點(diǎn)的個(gè)數(shù)n=x;//須修改}intmaxflow=0;d[src]=n;//源點(diǎn)高度為n//queue<int>q;priority_queue<List>q;//優(yōu)先隊(duì)列}elsemind=min(mind,d[v]);//不可推}d[u]=mind+1;}}}1.6.7最小割//vis[]=1為S集合的元素,vis[]=0為T集合的元素vis[u]=1;}01規(guī)劃：h n2的無向邊變成兩條容量為邊權(quán)w的有向邊，源點(diǎn)到每個(gè)點(diǎn)連邊邊，容量為U=2Σp+Σw，每個(gè)點(diǎn)向匯點(diǎn)連邊，對于點(diǎn)v，容量為v?2pv,dv為Σwe，pv為點(diǎn)v的權(quán)值，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考慮在自由流組成的網(wǎng)絡(luò)中求得可行流,然后累加上每條邊的下界來得到可行流,但這樣無法保證每個(gè)點(diǎn)的流量平衡。于是需要加入附加出去的多,所以由附加源向u連一條容量為M入的多,所以由點(diǎn)u向附加匯連一條容量為-M[u]的邊,保證點(diǎn)u多流然后保留原圖的邊,容量改為自由流,這樣在有附加源匯的新圖能夠達(dá)的可行流同時(shí)使得源匯也滿足流量平衡的條件,于是采用無源匯上下方法一:按有源匯上下界可行流方法判斷可行流是否存在,若存在則對原圖的源點(diǎn)和匯點(diǎn)做一遍最大流,擴(kuò)大之前的可行流,每條邊的實(shí)際流量,而是要多減去一個(gè)inf,因?yàn)榈谝槐榕袛嗫尚辛鲿r(shí),加了一條匯點(diǎn)第二遍求最大流時(shí),第一次被增廣的流量又回到匯點(diǎn),因此源點(diǎn)通過這取決于是否刪除附加源和附加匯,若刪除了則需加上下界,否則因?yàn)樵袋c(diǎn)連出的下界和已記錄在源點(diǎn)連向附加匯的邊上,并且在第一遍判可行流時(shí)已被增廣,所以無需再加(是否在做第二遍最大流前刪除附加源和附加匯以及它們的所有連邊并不影響第二遍的增廣,因?yàn)椴淮嬖趶脑袋c(diǎn)經(jīng)過這些邊到匯點(diǎn)的增廣路,只是如果不刪除的話,源點(diǎn)和匯點(diǎn)(包括那些下界出入不平衡的中間點(diǎn))的相鄰邊會(huì)增加,也就是上面討點(diǎn)到源點(diǎn)的這條邊,也并沒有大的影響,因?yàn)檫@條邊必然會(huì)被增廣完,方法二:二分匯點(diǎn)連向源點(diǎn)這條邊的下界,然后判斷無源匯上下界網(wǎng)絡(luò)流是否存在可行流,因?yàn)槿舳窒陆缧∮诘扔谧畲罅鞯葍r(jià)于存在可方法一:與最大流類似,先判斷可行流是否存在。若存在,則以原圖的匯點(diǎn)作為源點(diǎn),以原圖的源點(diǎn)作為匯點(diǎn),邊不改變,做一遍反向最大流,實(shí)際對原圖來說是在不斷地減少可行流,當(dāng)反向達(dá)到最大,則正向剛好流,同樣注意如果刪掉附加源和附加匯以及它們的所有連邊,那么最小流還需要加上源點(diǎn)連出去邊的下界,并且由于是方向增廣,因此匯點(diǎn)連向源點(diǎn)的邊增廣完全,因此對源點(diǎn)來說這條邊的反向邊剛好為0,所以方法二:二分匯點(diǎn)連向源點(diǎn)這條邊的上界,然后判斷無源匯上下界網(wǎng)絡(luò)流是否存在可行流,因?yàn)槿舳稚辖绱笥诘扔谧钚×鞯葍r(jià)于存在可方法三:和判斷有源匯上下界可行流一樣建圖,但是需要分兩個(gè)階段,第一階段是不需要加匯點(diǎn)連向源點(diǎn)的邊(下界為0,一遍附加源到附加匯的最大流;第二階段是加上匯點(diǎn)連向源點(diǎn)的邊,然后再跑一遍附加源到附加匯的最大流,如果滿流,那么最小流剛好為匯點(diǎn)連向源點(diǎn)的這條邊的流量,否則不存在可行流?？梢赃@么理解,只要最后補(bǔ)齊的圖一樣,分階段增廣與一步增廣最后達(dá)到的效果是一樣的,因此判斷是否存在可行流依然成立。我們可以考慮下為什么要加匯點(diǎn)到源點(diǎn)的這條邊,本質(zhì)是因?yàn)樵磪R不滿足流量平衡的條件,因此加入附加源和附加匯建立的圖除源匯點(diǎn)外,在增廣自由流后得到的偽流和下界疊加后剛好得到可行流,但這樣的前提是強(qiáng)制考慮自由流可以流動(dòng),實(shí)際因?yàn)閰R點(diǎn)并不平衡,因此這些被強(qiáng)制考慮流動(dòng)的自由流應(yīng)囤積在匯點(diǎn),然而真正在增廣的圖的匯點(diǎn)是附加匯,因此不會(huì)有流囤積在原圖的匯點(diǎn),也就是自由流并不會(huì)流動(dòng),那么我們強(qiáng)制在匯點(diǎn)到源點(diǎn)連流向源點(diǎn),并且這樣做剛好使得源匯也流量平衡,成為無源匯網(wǎng)絡(luò)。那么要得到最小流,我們的想法是盡量使得囤積在匯點(diǎn)的流量減少,因此,第一階段不加這條邊,是想借用網(wǎng)絡(luò)本身的結(jié)構(gòu)讓附加源的流量盡量流向附加匯,這種情況會(huì)出現(xiàn)是原圖中存在回路(也就是電路當(dāng)中的短路情況),這樣便能盡量增廣一部分,而剩余的一部分只能通過第二階段來增廣了,于是如果原圖中不存在短路情況,那么可以省去第一階段,head[u]=tot++;}}vis[u]=0;vis[v]=1;}}//returndist[t]<0;//最小費(fèi)用流可行流}intalpha=inf,ans=0;alpha=min(alpha,p[i].cap);//可改進(jìn)量for(inti=from[t];i!=-1;i=from[p[i].from]){//增廣}}intans=0;}1.7.1基本概念/*支配與支配集:設(shè)無向圖G(V,E),V?為V的子集,對于?v∈(V?V?),?U∈V?,使得(u,v)∈E,稱u支配v，并稱V?為G的一個(gè)點(diǎn)支配集(簡稱支配集)點(diǎn)覆蓋集:設(shè)無向圖G(V,E),V?為V的子集,若對于?e∈E,?v∈V?,使得v與e相關(guān)聯(lián),則稱v覆蓋e,并稱V?為G的一個(gè)點(diǎn)覆蓋集(簡稱點(diǎn)覆蓋)點(diǎn)獨(dú)立集:設(shè)無向圖G(V,E),V?為V的子集,若V?中任何兩個(gè)頂點(diǎn)均不相鄰,則稱V?為G的點(diǎn)獨(dú)立集(簡稱獨(dú)立集)團(tuán):設(shè)無向圖G(V,E),V?為V的子集,且V?是完全圖覆蓋與邊覆蓋集:設(shè)無向圖G(V,E),E?為E的子集，若與e相關(guān)聯(lián),則稱e覆蓋v,并稱E?為邊覆蓋集(簡稱邊覆蓋)配蓋點(diǎn)與未蓋點(diǎn):設(shè)v是圖G的一個(gè)頂點(diǎn),如果v與匹配M中的某條邊關(guān)聯(lián),則稱v是M的蓋點(diǎn)(M飽和點(diǎn));如果v不與任意一條屬于匹配M的邊相關(guān)聯(lián),則稱v是匹配M的未蓋點(diǎn)(非M飽和點(diǎn))的定義矛盾;大點(diǎn)獨(dú)立集了→{α0+β0=n,n為頂點(diǎn)數(shù)}定理5:在無向圖G中,V?是G的團(tuán),當(dāng)且僅當(dāng)V?是G的補(bǔ)圖的獨(dú)立集推論:在無向圖G中,V?是G的極大(最大)團(tuán),當(dāng)且僅當(dāng)V?是G的補(bǔ)圖的極大(最定理6:設(shè)無向圖G的頂點(diǎn)個(gè)數(shù)為n,且G中無孤立點(diǎn)⑴設(shè)M為G的一個(gè)最大匹配,對于G中M的每個(gè)未蓋點(diǎn)v,選取一條與v關(guān)聯(lián)的邊所組成的集合為N,則W=M∪N為G中的最小邊覆蓋⑵設(shè)W為G的最小邊覆蓋,若G中存在相鄰的邊就移去其中的一條,設(shè)移去的邊集為N,則M=W-N為G中一個(gè)最大匹配⑶G中邊覆蓋數(shù)α1與匹配數(shù)β1,滿足α1+β1=n其他性質(zhì):公式:α0+β0=n無孤立點(diǎn)有X部未做標(biāo)記的點(diǎn)和Y部做好標(biāo)記的點(diǎn)組成了最小點(diǎn)覆蓋集將所有的點(diǎn)拆成兩個(gè)點(diǎn),V拆成Vx和Vy,原圖中有邊A->B,新圖中添加圖合并兩條路徑.并且由于是匹配,X部的每個(gè)點(diǎn)最多連出去一條邊到Y(jié)部,對應(yīng)原圖這些點(diǎn)的出度至多為1,同理Y部的每個(gè)點(diǎn)最多來自X部一條邊,對應(yīng)原圖每適用有向無環(huán)圖*/1.7.2最大團(tuán)intcq[Maxn];//當(dāng)前最大團(tuán)序列,下標(biāo)從0開始intclique[Maxn];//最終最大團(tuán)序列,下標(biāo)從0開始intans;//最大團(tuán)數(shù)if(tot>ans){//每次增加1個(gè)點(diǎn),最大團(tuán)數(shù)最多增加1//需要序列}if(adj[u][v]){//取點(diǎn)vif(!adj[cq[w]][v]){//點(diǎn)v與已有最大團(tuán)不相容}}}}ans=0;cq[0]=i;//選擇點(diǎn)icnt[i]=ans;//更新cnt}}/*****復(fù)雜度O(n^3)*****/intadj[Maxn][Maxn];//鄰intmatch[Maxn];//match[i]表示y組i與x組match[i]匹配intdeep;//優(yōu)化vis數(shù)組for(intv=1;v<=y;v++){//掃描y組,下標(biāo)[1,y]}}}intans=0;for(inti=1;i<=x;i++){//掃描x組,[1,x]}}/*****復(fù)雜度O(n^3)*****/intadj[Maxn][Maxn];//鄰intmx[Maxn];//X匹配Yintmy[Maxn];//Y匹配Xintq[Maxn];//BFS隊(duì)列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)/*****復(fù)雜度O(n^2.5)*****/intadj[Maxn][Maxn];//鄰intdx[Maxn],dy[Maxn];//X/Y的層次intmx[Maxn],my[Maxn];//X/Y匹配Y/Xintq[Maxn];//BFS隊(duì)列intdeep;//優(yōu)化vis數(shù)組for(inti=1;i<=x;i++)//掃描X組}for(intv=1;v<=y;v++){//掃描Y組dy[v]=dx[u]+1;//更新距離else{//從my[v]繼續(xù)往下增廣}}}for(intv=1;v<=y;v++){//掃描Y組}}}intans=0;deep=0;if(mx[i]==-1){//未蓋點(diǎn)deep++;}}}1.7.6完全二分圖的最大匹配(KM)/***復(fù)雜度O(n^3)***/intadj[Maxn][Maxn];//鄰intmatch[Maxn];//match[i]表示X組i與Y組match[i]匹配intlx[Maxn],ly[Maxn];//X和Y部的標(biāo)號(hào),輔助作用intvx[Maxn],vy[Maxn];//X和Y部的點(diǎn)是否被訪問intmn[Maxn];//mn[i]表示y組i與交錯(cuò)路上的X組點(diǎn)邊權(quán)最小值intx,y;//X和Y部的點(diǎn)數(shù)intdep;//優(yōu)化vx和vy數(shù)組vx[u]=dep;for(intv=1;v<=y;v++){//掃描y組,下標(biāo)[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,可能在后面會(huì)減小//INF不能太小,以防爆intx=n,y=m;//不要忘記給x,y賦值,x<=yadj[i][j]=INF;}1.8.1基本概念/*K5(5階完全圖),K3,3(完全二部點(diǎn)和邊的范圍區(qū)域的邊界)區(qū)域i與區(qū)域j有公共邊,則連接這兩個(gè)區(qū)域?qū)?yīng)的點(diǎn),若原平面圖有橋(性質(zhì):定理4:設(shè)G為n(n>=3)階簡單連通的平面圖,G為極大平面圖當(dāng)且僅當(dāng)G的每個(gè)區(qū)域度數(shù)為3定理5:設(shè)G*是連通平面圖G的對偶圖,n*,m*,r*和n,m,r分別為G*和G的頂點(diǎn)數(shù)、⑷設(shè)頂點(diǎn)vEQ\*jc3\*hps17\o\al(\s\up4(*),i)位于G的區(qū)域Ri,則deg(vEQ\*jc3\*hps17\o\al(\s\up4(*),i))=deg(Ri),即對偶圖中頂點(diǎn)vEQ\*jc3\*hps17\o\al(\s\up4(*),i)的度數(shù)等定理6:如果G是一個(gè)階n>=3,邊數(shù)為m的平面圖,則m<=3n-6推論1:如果G是一個(gè)階n>=3,邊數(shù)為m>3n-6的圖,則圖G是非平面圖推論2:每個(gè)平面圖都含有一個(gè)小于等于5的頂點(diǎn)推論3:5階完全圖是非平面圖和(或)去掉度數(shù)為2的頂點(diǎn)后,使得G1和G2同構(gòu),則稱G1和G2是在2度頂點(diǎn)內(nèi)同構(gòu)的在2度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖收縮:設(shè)e是圖G的一條邊,從G中刪去e并將e的兩個(gè)頂點(diǎn)合并,刪除由此得到圖G2同構(gòu)的圖,則稱G1可以收縮到G2.注意,收縮邊e并不要求e的兩個(gè)頂點(diǎn)度數(shù)為2Wagner定理:圖G是平面圖,當(dāng)且僅當(dāng)G中既沒有可收縮到K5的子圖,也沒有可以收縮到K3,3的子圖歐拉公式:如果G是一個(gè)頂點(diǎn)數(shù)為n,邊數(shù)為m,面數(shù)為r的連通平面圖,則有恒等式:n-m+r=2*/1.9.1基本概念/*頂點(diǎn)顏色均不同色數(shù)(Χ(G)):如果能用k種顏色對圖G進(jìn)行頂點(diǎn)著色,就稱對圖G進(jìn)行了k著色,也稱G是k-可著色的.若G是k-可著色的,但不是(k-1)-可著色的,稱G是k色的圖,并稱這樣的k為圖G的色數(shù)定理1:Χ(G)=1當(dāng)且僅當(dāng)G是零圖(沒有邊的圖)定理2:n階完全圖的色數(shù)為n定理3:奇圈的色數(shù)為3定理4:圖G的色數(shù)為2當(dāng)且僅當(dāng)G是一個(gè)非空的二部圖邊色數(shù)(Χ1(G)):如果能用k種顏色對圖G進(jìn)行邊著色,就稱對圖G進(jìn)行了k邊著色,也稱G是k-邊可著色的.若G是k-邊可著色的,但不是(k-1)-邊可著色的,稱G是k邊色的圖,并稱這樣的k為圖G的邊色數(shù)定理1:設(shè)圖G為長度大于或等于2的偶圈,則Χ1(G)=Δ(G)=2;設(shè)圖G為長度大于或等于3的奇圈,則Χ1(G)=Δ(G)+1=3面色數(shù)(Χ*(G)):如果能用k種顏色給平面圖G進(jìn)行面著色,則稱G是k-面可著色定理1:平面圖G是k-面可著色的,當(dāng)且僅當(dāng)它的對偶圖G*是k色的圖*/1.9.2順序染色(不一定是最優(yōu)解)/*****復(fù)雜度O(n^2)*****/intcolor[Maxn];//color[i]表示點(diǎn)i染的顏色intans=-1;//需要染色最大標(biāo)號(hào),從0開始memset(color,-1,sizefor(intj=0;j<n;j++)//標(biāo)記點(diǎn)i的鄰接點(diǎn)染過的顏色color[i]=j;//給點(diǎn)i染色ans=max(ans,j);//更新答案}}/*****復(fù)雜度O(n^2)*****/intcolor[Maxn];//color[i]表示點(diǎn)i染的顏色intans=-1;//需要染色最大標(biāo)號(hào),從0開始memset(color,-1,sizefor(intj=0;j<n;j++)//標(biāo)記點(diǎn)i的鄰接點(diǎn)染過的顏色color[i]=j;//給點(diǎn)i染色ans=max(ans,j);//更新答案}}1.9.3平面圖暴力染色(最優(yōu)解)/*****復(fù)雜度O(3^n)*****/intcolor[Maxn];//color[i]表示點(diǎn)i染的顏色intn;//頂點(diǎn)數(shù)boolcheck(intu,intc){//判斷u是否可以染成顏色cif(adj[u][v]&&color[v]==c)//沖突}voiddfs(intd){//最多只染3種顏色//當(dāng)color中的最大元素最小時(shí),染色連續(xù)ans=min(ans,*max_element(color}}//在主函數(shù)里加memset(adj,0,sizeofadj)//調(diào)用solve前構(gòu)造好鄰接矩陣color[0]=1;//點(diǎn)0染成顏色1dfs(1);//從點(diǎn)1開始染色}/*****復(fù)雜度O(E)*****/intto,next,w;inttot;intc[Maxn];//染色1,2head[a]=tot++;}c[1]=1;//染色第一個(gè)點(diǎn)要在dfs外初始化booldfs(intu){//dfs黑白染色intv=p[i].to;}}}2.1.1塊狀數(shù)組inta[Maxn];//存元素voidmaintain(intx){//維護(hù)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<}}/***復(fù)雜度sqrt(n)***///塊x對應(yīng)的區(qū)間[x*sz,(x+1)*sz-1]inta[Maxn];//原數(shù)組inttag[Maxn];//標(biāo)記intpos[Maxn];//pos[i]表示i所在的塊號(hào)voidmaintain(intx){//維護(hù)塊x的性質(zhì)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數(shù)組初始化for(inti=0;i<m;i++)tag[i]=0;}voidupdate(intx,inty,intv){//區(qū)間[x,y]加上v}//x,y所在塊暴力for(inti=pos[x]+1;}}//區(qū)間[x,y]大于等于v的個(gè)數(shù)統(tǒng)計(jì)intans=0;}//x,y所在塊內(nèi)暴力統(tǒng)計(jì)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變成該塊的個(gè)數(shù)blocklist*get_pos(int&x){//獲得第x個(gè)元素在ret塊的位置}}boolmerge(blocklist*pos){//合并pos和pos->nextmemmove(pos->num+pos->sz,pos->next->num,sizeof(int)}}}//一般先調(diào)用get_pos,使x變成該塊的個(gè)數(shù)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大于塊表元素總數(shù),插在表尾voidinsert(intx,intn){//將n個(gè)元素插入到x所在的位置,x后挪blocklist*pos=get_pif(!head)head=pos;//空表插入else{//x大于塊表元素總個(gè)數(shù)blocklist*it;//表尾插入}blocklist*tmp=pos-}scanf("%d",&pos->num[pos->sz++]);//讀入方式}maintain();//維護(hù)鏈表}voidremove(intx,intn){//刪除x后(包括x)的n個(gè)元素,刪除區(qū)間[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個(gè)數(shù)的和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;//按塊計(jì)算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}/*****復(fù)雜度O(n*α(n))*****/}intfindset(intx){//遞歸版}while(x!=r){i=fa[x];fa[}voidunionset(intx,inty){//rank[y]++;}}}}voidunionset(intx,i}voiddel(intx){//刪除x就是更改x的時(shí)間戳}intfa;//父親intdep;//深度}intrt[Maxn];//根}}//返回以數(shù)組下標(biāo)k為根的子樹中pos的下標(biāo)intmid=l+r>>1;}//只需復(fù)制一份從根(數(shù)組下標(biāo)為k)到葉子u的一條路徑//修改tr[t].fa=vif(l==r){//找到u,對應(yīng)新的節(jié)點(diǎn)ttr[t]=PUFD(v);//修改父親指向v}intmid=l+r>>1;}//返回以數(shù)組下標(biāo)k為根的子樹中pos的父親下標(biāo)}//修改以數(shù)組下標(biāo)k為根的子樹中pos對應(yīng)的深度if(l==r){//找到pos對應(yīng)節(jié)點(diǎn),深度+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//行數(shù)#defineMaxc370//列數(shù)/***DancingLinksX算法***/intL[Maxn],R[Maxn],U[Maxn],D[Mvoidinit(intm){//m為列數(shù)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){//恢復(fù)c列D[U[j]]=U[D[j]]=j,s[col[j}/*調(diào)用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(){//數(shù)組建堆}priority_queue<int>h,d;//h存所有元素,d存刪除的元素voidadd(intx){//插入xvoiddel(intx){//刪除xvoidfix(){//將已刪除的元素彈出hwhile(d.size()&&h.top()==d}intfirst(){//堆頂}voidpop(){//彈出堆頂}2.6樹形結(jié)構(gòu)2.6.1樹狀數(shù)組//x從1開始