acm icpc培訓(xùn)匯編4圖論分冊(cè)號(hào)

編寫說(shuō) 第3章圖 圖的基本概 圖的表 廣度優(yōu)先搜 深度優(yōu)先搜 拓?fù)渑?基本原 模板代 經(jīng)典題 活動(dòng)網(wǎng)絡(luò)(AOE網(wǎng)絡(luò) 最小生成樹 基本原 模板代 經(jīng)典題 最小生成樹 基本原 模板代 經(jīng)典題 最短路 基本原 模板代 經(jīng)典題 基本原 模板代 經(jīng)典題 所有頂點(diǎn)之間的最短路 基本原 模板代 經(jīng)典題 差分約束與最短 基本原 解題思 經(jīng)典題 最大 基本原 解題思 模板代 經(jīng)典題 最小費(fèi)用最大 基本原 模板代 經(jīng)典題 有上下界的最大 基本原 經(jīng)典題 樹的最小支配集，最小點(diǎn)覆蓋與最大獨(dú)立 基本原 模板代 二分圖最大匹 基本原 解題思 模板代 經(jīng)典題 強(qiáng)連 基本原 解題思 模板代 經(jīng)典題 重連 基本原 解題思 模板代 經(jīng)典題 2- 基本原 解題思 模板代 經(jīng)典題 第3編寫 圖的概念類似于地圖，地圖上有城市和道路，圖可以用來(lái)表示一個(gè)集合以及這些之間的關(guān)系，可以指實(shí)在的物體、城市、或某些狀態(tài)等，對(duì)應(yīng)的關(guān)系則為物體之間的聯(lián)系、交通道路、狀態(tài)之間的轉(zhuǎn)換關(guān)系等等。叫做頂點(diǎn)，關(guān)系叫做邊。圖是一個(gè)從邊數(shù)上，可以分為稠密圖和稀疏圖。假設(shè)一個(gè)圖中的頂點(diǎn)數(shù)為V，那么如果兩個(gè)點(diǎn)n*(n-1)/2條邊，如果要求所有的點(diǎn)之間都是可達(dá)的，那么最少要求有n-1條邊，可以看到，最多和最少邊數(shù)相差很大，所以稀疏圖和稠密唯一性，拓?fù)渑判虻臒o(wú)回路性，最短路的的無(wú)負(fù)權(quán)，無(wú)負(fù)環(huán)，0頂點(diǎn)圖或單頂點(diǎn)圖等等。圖的鄰接矩陣使用一個(gè)二維矩陣，矩陣的兩個(gè)維度均為圖的頂點(diǎn)數(shù)，下標(biāo)表示頂點(diǎn)的編graph[N][Ngraph[i]j表示i頂j0graph[i][j]graph[i[j]==graph[j][i。使用鄰接矩陣表示無(wú)權(quán)圖時(shí)可以使用boolchar型數(shù)據(jù)來(lái)達(dá)到節(jié)省內(nèi)存的目的。123541234525315123541234525315242534-124O(n^2)O(V+E)，所以鄰接表在稀疏struct{intnext_arc;intpoint;intnode[V];structArcarc[E];使用node每個(gè)頂點(diǎn)，arc每條邊，node[i]表示第i個(gè)頂點(diǎn)指向的第一條邊arc中的位置，next_arc表示和這條邊同樣出發(fā)點(diǎn)的下一條邊在arc中的位i是在該鏈表上插入一個(gè)節(jié)點(diǎn)，這里的鏈表是用數(shù)組實(shí)現(xiàn)，當(dāng)然也可以使用動(dòng)態(tài)分配去實(shí)現(xiàn)。voidAddEdge(intu,int{}EdgeCount用來(lái)表示總共加入的邊的數(shù)量，初始化為廣度圖的搜索是對(duì)一個(gè)圖進(jìn)行有序的遍歷，以獲得圖中的有用信息，搜索是圖論算法的從圖的一個(gè)頂點(diǎn)出發(fā)，首先該點(diǎn)，然后依次從該點(diǎn)出發(fā)指向的那些點(diǎn)，再按的順序依次那些點(diǎn)所指向的點(diǎn)，比如上圖：從1點(diǎn)出發(fā)，首先1，然1指向的2、5，再2指向的3、4，再去5指向的點(diǎn)，而5指向的4已經(jīng)被廣度優(yōu)先搜索使用隊(duì)列實(shí)現(xiàn)，每次將當(dāng)前節(jié)點(diǎn)指向的未節(jié)點(diǎn)依次加入隊(duì)列，比如在1的時(shí)候依次將2、5入隊(duì)，1后將2從隊(duì)列中取出，再將與2相連的3、4入隊(duì)，這樣即實(shí)現(xiàn)了“一層一層”去遍歷一個(gè)圖，類似于二叉樹的層次遍歷。間復(fù)雜度為O(V+E)。intvis[V];//標(biāo)記數(shù)組，vis[i]==1表示i已入隊(duì)，0表示未入隊(duì)intfront,rear;//隊(duì)首和隊(duì)尾指針void{que[rear++]=0;//假設(shè)從0號(hào)頂點(diǎn)開始廣度搜索，實(shí)際也可能沒(méi)有0號(hào)頂//根據(jù)實(shí)際情況決定{intcur_node=que[front++];//取隊(duì)首頂點(diǎn)intedge;{{}}}}深度首先從1點(diǎn)出發(fā)，2點(diǎn)，再3點(diǎn)、4點(diǎn)、5點(diǎn)，然后無(wú)法繼續(xù)前進(jìn)了，就退回，判斷4點(diǎn)是否有除5點(diǎn)以外可的未點(diǎn)，有的話再前進(jìn)，沒(méi)有就繼續(xù)回退。intvis[V];voiddfs(intv){intfor(edge=node[v];edge!=-{{}}}編寫：校核基本對(duì)一個(gè)有向無(wú)回路圖進(jìn)行拓?fù)渑判蚝?，所有的頂點(diǎn)形成一個(gè)序列，對(duì)所有邊(u,v)，滿足u在v的前面。該序列說(shuō)明了頂點(diǎn)表示的或狀態(tài)發(fā)生的整體順序。比較經(jīng)典的是在工程對(duì)一個(gè)DAG進(jìn)行拓?fù)渑判蛴袃煞N方法，分別利用廣度優(yōu)先搜索與深度優(yōu)先搜索。0的點(diǎn)，即沒(méi)有被指向的點(diǎn)，因?yàn)檫@樣的點(diǎn)表示的沒(méi)有依賴，在一個(gè)入度為0的點(diǎn)表示的執(zhí)行0的點(diǎn)加入10的點(diǎn)也依次加入隊(duì)DAGu,v，一定有vuDFSu,vuv前面，所以可以利用DFS，將所有的點(diǎn)按照退出DFS的過(guò)程倒序排列，即得到一個(gè)圖的拓?fù)?2123456取隊(duì)首，即3頂點(diǎn)，將2、6的入度減112、412、40.加入隊(duì)列26160，也加入隊(duì)列取隊(duì)首4頂點(diǎn)，4頂點(diǎn)沒(méi)有指向任何頂點(diǎn)剩下的點(diǎn)的搜索順序可以是3、5或者5、3這樣根據(jù)搜索結(jié)束的順序，即可以得到一個(gè)該圖的拓?fù)湫颍?、5、1、2、6、4模板struct{intpoint;intnext_arc;Arcarc[50005];intnode[5005];intdigree[5005];inttop[5005];int{intn,m;for(int{inta,b;}for(int{{}}intl=0;{intx=q.front();{{}}}return}經(jīng)典HDOJN個(gè)比賽隊(duì)（1<=N<=5001，2，3N進(jìn)行比賽，比賽結(jié)束后，裁判要將所有參賽隊(duì)伍從前往后依次，但現(xiàn)在裁判不能直接獲得每?jī)蓚€(gè)編號(hào)小的要面，這點(diǎn)可以通過(guò)將普通拓?fù)渑判蛑械年?duì)列改為使用優(yōu)先隊(duì)列或者堆usingnamespacestd;intgraph[505][505];//表示圖的數(shù)組intdigree[505];//每個(gè)頂點(diǎn)的入度int{intn,m;{for(int{intu,v;if(!graph[u][v])//此處要注意，防止有重復(fù){}}使用從小到大，注意最后一個(gè)>前面的空格，這個(gè)必須有for(int{}boolfirst=1;{intcur=q.top();elsecout<<''<<cur;for(int{{{}}}}}return}活動(dòng)網(wǎng)絡(luò)(AOE網(wǎng)絡(luò)編寫 校核AOE網(wǎng)絡(luò)是指用邊表示活動(dòng)的網(wǎng)絡(luò)，用弧表示一個(gè)活動(dòng)，弧頭表示活動(dòng)結(jié)束，弧尾表示活動(dòng)開始，弧長(zhǎng)表示活動(dòng)所需時(shí)間，每個(gè)頂點(diǎn)叫做一個(gè)，表示以其為弧尾的活動(dòng)的AOE網(wǎng)絡(luò)中的問(wèn)題一般為求解在一個(gè)活動(dòng)網(wǎng)絡(luò)中所有活動(dòng)全部完成所需的最少時(shí)間及例如用下圖的網(wǎng)絡(luò)表示一項(xiàng)工程，每條弧表示工程中的一個(gè)環(huán)節(jié)，弧長(zhǎng)表示完成該環(huán)節(jié)所需時(shí)間，要求完成該項(xiàng)工程所需時(shí)間，顯然就是要求從開始頂點(diǎn)到結(jié)束頂點(diǎn)所經(jīng)過(guò)的最長(zhǎng)路徑，因?yàn)閳D是有向無(wú)回路圖（G，所以可以使用拓?fù)渑判蚣觿?dòng)態(tài)規(guī)劃的方法解出該時(shí)間。以a[i]表示第i個(gè)的最早開始時(shí)間，a[0]為0，對(duì)原圖進(jìn)行拓?fù)渑判颍谌〕鲆粋€(gè)0的頂點(diǎn)之后要對(duì)它所指向的點(diǎn)的入度進(jìn)行更新，在此時(shí)同時(shí)更新被指向的點(diǎn)所表示的完成所需時(shí)間為指向它的點(diǎn)所需完成時(shí)間+弧長(zhǎng)最大的一個(gè)，如在找出入度為0的頂點(diǎn)i的時(shí)候?qū)?i,j)進(jìn)行更新，首先更新點(diǎn)j的入度為原值減1，然后執(zhí)行而要找出影響該時(shí)間的關(guān)鍵活動(dòng)，則需要知道哪些活動(dòng)的開始時(shí)間是不能推遲的，這里可以通過(guò)上面已經(jīng)求得的項(xiàng)目完成時(shí)間，從結(jié)束點(diǎn)開始向開始點(diǎn)進(jìn)行逆向拓?fù)渑判颍诒敬瓮負(fù)渑判蛑星蟮妹總€(gè)頂點(diǎn)表示的的最晚開始時(shí)間，然后判斷每個(gè)點(diǎn)的開始時(shí)間和最晚開始時(shí)間，如果兩個(gè)時(shí)間值相等，則說(shuō)明該以該開始的某些活動(dòng)是不能推遲的，這樣的活動(dòng)所組成的從開始點(diǎn)到結(jié)束點(diǎn)的路徑叫做關(guān)鍵路徑，關(guān)鍵路徑上的每一個(gè)都滿兩個(gè)時(shí)間相等，這樣的路徑上的弧所表示的活動(dòng)都是影響項(xiàng)目完成速度的活動(dòng)。編寫：校核在對(duì)一個(gè)無(wú)向圖進(jìn)行遍歷時(shí)，根據(jù)遍歷時(shí)每個(gè)頂點(diǎn)的前趨頂點(diǎn)和后繼頂點(diǎn)間的關(guān)系，保留搜索時(shí)經(jīng)過(guò)的邊而放棄回邊（即搜索時(shí)當(dāng)前點(diǎn)與一個(gè)已搜索過(guò)的點(diǎn)之間的邊，可以得到一棵樹，該樹叫做圖的生成樹。生成樹包含原圖中的所有頂點(diǎn)（V個(gè)V-1條邊，它保證了無(wú)向圖中N-1條邊有一個(gè)權(quán)值和，使這個(gè)權(quán)值和最小的生成基本構(gòu)造最小生成樹的Prim算法將原圖的頂點(diǎn)分為兩部分，假設(shè)原頂點(diǎn)集為VSV-S，S為已經(jīng)確定在最小生成樹中的頂點(diǎn)，在算法的最初將任意一個(gè)節(jié)點(diǎn)作為S中的唯V-SS中的點(diǎn)最近的一個(gè)頂點(diǎn)，作為下一個(gè)加入最小N個(gè)節(jié)點(diǎn)全部加入到最小生成樹中后，最小生成樹構(gòu)造完畢。對(duì)于一個(gè)使用鄰接矩陣的圖graph[N][N]，可以使用一個(gè)數(shù)組low[N]保存每個(gè)頂點(diǎn)到已low值，直到所 3541作為生成樹的第一個(gè)點(diǎn)，然后計(jì)算每個(gè)點(diǎn)距離該未完成的樹中頂點(diǎn)的最小距離，66的距離是否比原來(lái)到生成樹的65255加入生成樹，4、3、2、7，分別加入最小生成樹中，最小生成樹構(gòu)成完畢，需要最小代價(jià)也N個(gè)點(diǎn)，每次加入時(shí)尋找最近點(diǎn)需要遍歷每個(gè)點(diǎn)，更新也需要遍歷每個(gè)點(diǎn)，所以Prim需要O(N^2)的時(shí)間。Prim算法對(duì)于使用鄰接矩陣表示的圖來(lái)說(shuō)非常方便實(shí)現(xiàn)，所以在求稀疏圖的最小生成樹的時(shí)候常用Prim算法。模板//prim函數(shù)返回得到的最小生成樹的n-1條邊的權(quán)//參數(shù)cost為表示圖的矩陣，n為頂點(diǎn)intprim(intcost[][200],int{//low表示每個(gè)點(diǎn)到生成樹的最小距離，vis表示一個(gè)點(diǎn)是否已加入生成intlow[10000],vis[10000]={0};inti,j,p;intmin,res=0;{{{}}//min==INF說(shuō)明找不到能夠加入的點(diǎn)了，說(shuō)明圖是不連{{}}}return}經(jīng)典HDOJN1-N，你現(xiàn)在要去建一些街道，使每?jī)蓚€(gè)村莊之間都能夠連通，如果A、BC，CACB之間都有街道相usingnamespacestd;//prim函數(shù)返回得到的最小生成樹的n-1條邊的權(quán)//參數(shù)cost為表示圖的矩陣，n為頂點(diǎn)intprim(intcost[][200],int{//low表示每個(gè)點(diǎn)到生成樹的最小距離，vis表示一個(gè)點(diǎn)是否已加入生成intlow[10000],vis[10000]={0};inti,j,p;intmin,res=0;{{{}}//min==INF說(shuō)明找不到能夠加入的點(diǎn)了，說(shuō)明圖是不連{{}}}return}int{intint{for(int{for(int{}}intq;for(inti=0;i<q;i++){intu,v;a[u-1][v-1]=a[v-1][u-}intres=prim(a,n);}return}HDOJnm個(gè)頂點(diǎn)的子圖，并且讓這個(gè)子圖的Ratio值在所有m個(gè)頂點(diǎn)的樹中最小。mRatio最小，只要該nm個(gè)點(diǎn)的子圖，然后對(duì)這mRatiomRatiousingnamespacestd;#defineINF0x1f1f1f1f#defineMIN(a,b)#defineMAX(a,b)intedge_wei[20][20];//邊權(quán)intnode_wei[20];//點(diǎn)權(quán)boolflag[20];booldoubleres; boolarr[20];//resultarrayintn,m;{intintlow[20]={0};intsta;for(int{{}}for(int{{}}for(int{intmin=INF;intloc;for(int{{}}for(intj=1;j<=n;j++){{{}}}}return}voiddfs(int{ {intr=mst();intfor(int{{}}doubleres_tmp=(double)r/(double)sum;{for(int{}}}for(int{}t--}int{{for(int{}for(int{for(int{}}{}intfor(int{{{}{}}}

printf("}return編寫：校核基本V-1條邊，此時(shí)便構(gòu)O(ElogV)，空間復(fù)雜度為O(E)prim算法需要O(N^2)的時(shí)間和空間。Prim算法與Kruskal算法均使用了貪心思想模板intp[10005];//表示集合的數(shù)組intr[10005];//按秩合并所需的秩intfind(intv){returnp[v];}//并查集的合并voidjoin(intu,int{inta=find(u);intb=find(v);{}else{}{}}//初始化并voidinit_set(int{inti;{}structEdge{intu;intintstructEdge//快速排序，也可以使用qsortvoidquick_sort(structEdge*start,structEdge*{structEdge*loc=start;structEdge*itor;structEdgetmp; { tor->weight<(end-1)-{}}*loc=*(end-*(end-}intkru(intn,intm)//kruskal算法主要部分，傳入nm{inti;intcnt=0;//已加入最小生成樹的邊的數(shù)量{intu=edge[i].u;int{}if(cnt==n-1)returnret;//已找到n-1條邊，生成樹構(gòu)造}return-}經(jīng)典POJ1n點(diǎn)之間連接出一條路使用kruskalusingnamespacestd;struct{intu;intv;intboolcmp(Edgee1,Edge{return}Edge intp[1005];intintfind(int{returnp[u];}voidjoin(intu,int{inta=find(u);intb=find(v);elseif(r[a]<r[b])p[a]=b;{}}int{intintcse=1;{intn,m;for(inti=1;i<=n;i++){}for(int{}intres;for(int{intu=e[i].u;intv=e[i].v;{}}}return}usingnamespacestd;int inthead[1005];intnext[ int boolvoidadd_edge(intu,intv,int{ }void{dis[1]=0x1f1f1f1f;//源點(diǎn)要初始化成無(wú)窮，其他點(diǎn)初始化 {intu=q.front();{int{weight[e]，否則v點(diǎn)dis{{}}}

elseif(dis[v]<dis[u])//如果該邊權(quán)值大于vdis值，則vdis值為dis[u]、{{}}}}}int{intt;intsen=1;{{intu,v,w;}}return}編寫：校核在一個(gè)有向或無(wú)向圖中尋找兩個(gè)頂點(diǎn)間的某種代價(jià)最小的路徑的問(wèn)題稱為最短路問(wèn)題，如果只是需要求兩個(gè)點(diǎn)間的最短路或一個(gè)點(diǎn)到若干點(diǎn)間的最短路，則為單源最短路問(wèn)題，如果需要知道每?jī)蓚€(gè)頂點(diǎn)間的最短路，則為所有頂點(diǎn)間的最短路問(wèn)題?；緑0,v0v0v0沒(méi)有直接的邊相連的話，則一定要通過(guò)其它的點(diǎn)間接才能到達(dá)v0v0，所以v0v0的有邊直接相連并且距離最小的一v1,v0v1的最短距離即為邊(v0,v1)的權(quán)，而其他的頂v0v0v1間接到達(dá)v0的距離，此時(shí)我們需要對(duì)所有v1指向的邊進(jìn)行一次判斷，以確定它們是否可以通v2,v2v0的最短距離也可以得到確定，因?yàn)槠渌黺0v2v0也一定不短于n-1n-1個(gè)點(diǎn)的最短距離，因?yàn)檎业皆闯跏蓟袋c(diǎn)的最短距離為0，將源點(diǎn)插入一個(gè)優(yōu)先隊(duì)列（可以使用堆）中，優(yōu)先隊(duì)列中的元素需要保存頂點(diǎn)編號(hào)與該頂點(diǎn)到源點(diǎn)的距離，排序規(guī)則為距離小的（根據(jù)實(shí)際要求也可能大的。v1，對(duì)其指向的所有未確定最短距離的頂點(diǎn)v2，以邊(v1,v2)的權(quán)值+隊(duì)首元素的距離值和v2的編號(hào)構(gòu)造一個(gè)元素，并加入優(yōu)先隊(duì)列。Dijkstra算法的示例如上圖：灰色頂點(diǎn)為每次找到的被確定為最短路徑上的頂點(diǎn)，首ssy5t10y的最短距離確定后yys的最短距離+(y,t)ts的距離要離。但Dijkstra算法只能處理沒(méi)有負(fù)邊的情況，因?yàn)槿绻嬖谪?fù)邊，那么當(dāng)前確定的最短模板#defineINF0xfffffff#defineSIZE150intint{intboolflag[SIZE]={0};{}{intmin=INF;{{}}{}}}struct{intnext_arc;intpoint;intweight;intnode[N];structArcarc[M];voidinsert_edge(intu,intv,intweight,int{}structheap_elm{intnum;int//structheap_elmvoidinsert(structheap_elmh,int*len){inti=*len;{intj=(i>>1);{structheap_elm}else}}//調(diào)整堆使其保持堆voidheapfi(intloc,int{intleft=(loc<<1);intright=left+1;intmin_loc=loc;{}{}{structheap_elmtmp=heap[min_loc];}}//獲得堆頂structheap_elm{return}//刪除堆頂voiddel(int*{}intvis[N];//表示結(jié)果的數(shù)組，res[i]表示源點(diǎn)到i的最短int//Dijkstra算法主要部分，傳入頂點(diǎn)數(shù)n，邊數(shù)msrcvoiddij(intn,intm,intsrc){intlen=0;//初始化堆大小structheap_elmh;{intedge;for(edge=node[h.num];edge!=-{{structheap_elmt;}}}}經(jīng)典HDOJDijkstra算法練習(xí)題，只是多了一個(gè)條件，可以使用鄰接矩陣實(shí)現(xiàn)，但使用鄰接表+優(yōu)先隊(duì)列實(shí)現(xiàn)是最好選擇，SPFA亦可。usingnamespacestd;#defineINF0x1f1f1f1f#defineSIZE1005intdis[SIZE][SIZE];intcost[SIZE][SIZE];voidDIJ(intn,ints,int{boolflag[SIZE]={0};for(int{}intfor(int{intmindis=INF;intmincost=INF;for(int{{{}else{}}}for(int{{{}{}}}}}int{intn,m;{for(inti=1;i<=n;i++){}for(int{intu,v,d,c;{}}ints,t;}return} 因?yàn)閮蓚€(gè)人的時(shí)候會(huì)讓花費(fèi)變小，所以他們會(huì)先盡量，再在某處分開各自YY形的三條線路所需花費(fèi)之usingnamespacestd;#defineINF0x1f1f1f1f//無(wú)窮大，這里的無(wú)窮大不能太大，否則三個(gè)無(wú)窮大相加的時(shí)候會(huì)出現(xiàn)數(shù)據(jù)范圍溢出structstr//用于優(yōu)先隊(duì)列的元素{intnum;//在隊(duì)列中的元素所在的點(diǎn)intcost;//源點(diǎn)到該點(diǎn)的花費(fèi)str(intn,intc):num(n),cost(c){}//C++中的構(gòu)造函數(shù)friendbooloperator(strs1,strs2)//{return}struct{intnext_arc;intpoint;intcost;Arcarc[20005];inthead[5005];boolfl[5005];intlowa[5005];intlowb[5005];intlowc[5005];intC,A,B;{memset(fl,0,sizeof(fl));//標(biāo)記priority_queue<str>q;//這里用了STL的優(yōu)先隊(duì)列容器，使用堆有時(shí)會(huì)更快，建議自己寫堆intkk=0;{strfor(inte=head[s.num];e!=-{{}}}}int{intcse=1;intn,m;{memset(head,-for(inti=1;i<=m;i++){intx,y,k;}printf("Scenario#%d\n",cse++);intres=INF;{printf("Cannotreah!\n");}for(int{{}}}return}編寫：校核：基本v0v的最短距離，Dijkstra算法實(shí)際也使用了松弛操作，松弛是Bellan-Frd-1E度為(E)，源點(diǎn)到每個(gè)點(diǎn)的最短路徑中，最多經(jīng)過(guò)除它們以外的2個(gè)頂點(diǎn)，所以Bellan-Frd1次松弛嘗試，如果沒(méi)有負(fù)環(huán)存在，則最后一定可以確定源點(diǎn)到每個(gè)頂點(diǎn)的最短距離，包括有負(fù)邊存在的情況下。如果要判斷是否有負(fù)環(huán)存在，對(duì)于Bellan-Fd，可以運(yùn)行第二次算法，判斷是否還可再松弛，如果是，則說(shuō)明有負(fù)環(huán)存在，對(duì)于A，如果有負(fù)環(huán)，則隊(duì)列無(wú)法為空，因?yàn)槊總€(gè)頂點(diǎn)不可能入隊(duì)超NN次，則說(shuō)明有負(fù)環(huán)存在。因?yàn)槿绻麅蓚€(gè)頂點(diǎn)都是從源點(diǎn)不可達(dá)的邊，對(duì)其進(jìn)行松弛嘗試是沒(méi)有意義的，所以Bellman-Ford算法可以使用隊(duì)列進(jìn)行一定的改進(jìn)，每次只對(duì)當(dāng)前源點(diǎn)可達(dá)的頂點(diǎn)進(jìn)行松弛模板#defineN105intvoidbellman(intn,int{res[src]=0;//源點(diǎn)的最短距離為0inti,j,k;{//j、k所在循環(huán)為對(duì)每條邊進(jìn)行{{{}}}}}struct{intu;intv;intEdgeboolbellman(intn,intm,intsrc)//n點(diǎn)數(shù)，m邊數(shù)，src{//初始化每個(gè)頂點(diǎn)的最短距離res[src]=0;//源點(diǎn)的最短距離為0for(inti=0;i<n;i++){for(int{{}}}{for(int{{return}}}return}SPFA算法：#defineNintboolin_que[N];//標(biāo)記一個(gè)點(diǎn)是否已在隊(duì)列中intfront;//隊(duì)首位置voidspfa(intn,int{{intcur=que[++front];inti;{{{}}}}}struct{intnext_arc;intpoint;intintnode[5000];structArcarc[6000];{res[src]=0;//源點(diǎn)的最短距離為0{intc=q.front();fl[c]=0;//入隊(duì)標(biāo)記{{{if(cnt[arc[e].point]>=n)return1;}}}}return}經(jīng)典1.題目出處/ 有一個(gè)農(nóng)場(chǎng)，里面有一些奇怪的單向的蟲洞，通過(guò)蟲洞的到出口可以讓時(shí)間倒退，農(nóng)場(chǎng)主想知道他是否能夠通過(guò)農(nóng)場(chǎng)中的路和蟲洞走回出發(fā)點(diǎn)，并且使時(shí)間，給出N塊地、MW個(gè)蟲洞。Bellman-FordSPFA去usingnamespacestd;struct{intintv;intEdge{res[src]=0;//源點(diǎn)的最短距離為0for(inti=0;i<n;i++){for(int{{}}}for(int{for(int{{return}}}return}int{intf;{intn,m,w;for(inti=0;i<m;i++){ints,e,t;}for(int{ints,e,t;edge[i+2*m].u=s,edge[i+2*m].v=e,edge[i+2*m].t=-}elseprintf("NO\n");}return}這里使用的是SPFA的鄰接矩陣表示，如果使用鄰接表效率會(huì)更usingnamespacestd;#defineNintboolin_que[N];//標(biāo)記一個(gè)點(diǎn)是否已在隊(duì)列中intfront;//隊(duì)首位置boolspfa(intn,int{{intcur=que[++front];inti;{{{if(cnt[i]>=n)return1;}}}}return}int{intf;{intn,m,w;for(inti=0;i<m;i++){ints,e,t;}for(int{ints,e,t;}elseprintf("NO\n");}return}所有頂點(diǎn)之間的最短路編寫：校核基本kpp1～k-1kpi~kk~ji~j途經(jīng)頂點(diǎn)不超過(guò)k的最短距離，則g[k][i][j]=min(g[k-1][i][j],g[k-1][i][k]+g[k-1][k][j])kk-1將上式改為if(g[i][k]&&g[k][j])g[i][j]=1;可以用來(lái)解決有向圖的傳遞閉包問(wèn)題，這是一類用來(lái)尋找兩個(gè)元間是否存在某種可傳遞性的關(guān)系的問(wèn)題，比如兩個(gè)人之間是否有親ABBC也存在關(guān)系，那么就可以確定A和C也存在親屬關(guān)系。模板inti,j,k;{{{g[i][j]=min(g[i][j],g[i][k]+g[k][j]);//g為表示圖的鄰接}}}經(jīng)典/online12519TOMNN個(gè)城市的先后順序，給出每?jī)蓚€(gè)城市間的花費(fèi)，TOM想知道，按他的旅行順序去依次參觀這N個(gè)城市最少需要，每Nfloyd求出每?jī)蓚€(gè)城市間互相到達(dá)usingnamespacestd;#defineINF0x1f1f1f1fintn;intg[205][205];//每?jī)蓚€(gè)城市間的花費(fèi)inta[205];//城市的順序void{intfor(k=0;k<n;k++)for(i=0;i<n;i++)forif}int{intt;{for(inti=0;i<n;i++){}for(int{for(int{if(g[i][j]==-1)//如果是- 表示兩個(gè)城市不可直接到達(dá)，距離設(shè)為無(wú)窮{}}}{{}}{}{}}return} N，M，Q，N表示圖中的節(jié)點(diǎn)M表示邊的數(shù)量，M<=100000;Q表示執(zhí)行多少次操作，Q<=1000000,1,2,...,N-Mx,y,c,xy有一條邊長(zhǎng)度為c,c>0，然Q行，每行表示一次操作，0xx標(biāo)記，1xyxy的只通過(guò)N=M=Q=0是輸入結(jié)束。0xx已經(jīng)被標(biāo)記過(guò)了，輸出"ERRORAtpoint1xyxy沒(méi)有被標(biāo)記過(guò)，輸出"ERROR!Atpathxtoy"，如果無(wú)法從x通過(guò)標(biāo)記過(guò)的節(jié)y,輸出"Nosuchpath"路而且每?jī)蓚€(gè)點(diǎn)間的最短路都有可能求到，所以可以考慮使用floyd算法求出所有點(diǎn)間的最短路，而起初被標(biāo)記的點(diǎn)的數(shù)量是0，所以每?jī)蓚€(gè)點(diǎn)間的最短路都應(yīng)為無(wú)窮大，每次標(biāo)usingnamespacestd;intboolfl[305];//一個(gè)頂點(diǎn)是否被標(biāo)記intn,m,q;int{intcse=1;//第幾組數(shù)據(jù){{}for(int{inta,b,w;g[a][b]=(w<g[a][b]?w:g[a][b]);//防止重}for(int{intc,a,b;{{printf("ERROR!Atpath%dto}else{}{

}{}

printf("Nosuch{}{

printf("ERROR!Atpointfor(intj=0;j<n;j++){for(int{{}}}}}}}return}編寫 校核：基本考慮最短路問(wèn)題中的松弛部分，即對(duì)于某條邊(u,v)dis[v]<=dis[u]+(u,v)，dis為頂點(diǎn)實(shí)際距離源點(diǎn)的最短距離。于是可以根據(jù)不等式來(lái)構(gòu)造一個(gè)有向圖，以x[i]作為源點(diǎn)到i點(diǎn)的最短距離，x[i]-x[j]<=k中的k作為邊(j,i)的權(quán)值，使用最短路問(wèn)題的算法來(lái)解決差分約束問(wèn)題，由于差分約束方程構(gòu)造出的圖可能有負(fù)邊，所以比較適合使用Bellman-Ford或者SPFA算法來(lái)求得差分約束系統(tǒng)的一組解，如果出現(xiàn)負(fù)環(huán)，則說(shuō)明原方程組沒(méi)有可行解。解題經(jīng)典ZOJ題目描述的是劉備攻打陸遜時(shí)的連營(yíng)，輸入為大營(yíng)個(gè)數(shù)n，每個(gè)大營(yíng)中的最多士兵數(shù)Cii,j,kijk個(gè)。求劉備ijks[j]-s[i-1]>=k,s[i-1]-s[j]<=-k,即可知在對(duì)應(yīng)c[i]0s[i]-s[i-1]>=0s[i]-s[i-1]<=c[i]兩個(gè)不等式，根據(jù)這三類不等式，建立有向圖，利用Bellman-Ford或者SPFA求得頂點(diǎn)n到頂點(diǎn)0的最短路，即可得全部最少有多少士兵。usingnamespacestd;#defineEDGE_COUNT#definePNT_COUNT2000#defineINFstruct{intadj;intpoint;intweight;edge(inta,intp,intedgee[EDGE_COUNT];intint{for(int{for(int{{}}}for(int{{return}}return}int{intn,m;{for(int{}for(int{intu,v,w;e[i]=edge(v,u-1,-w);//u--v中最多有w個(gè)士兵，以i為邊的編}for(int{e[m+i]=edge(i-1,i,c[i]);//第i個(gè)中最多有c[i]個(gè)士兵m+i為這些邊的邊e[m+n+i]=edge(i,i-1,0);//并且最少有0士兵，m+n+i為這些邊的}elseprintf("BadEstimations\n");}return}編寫：校核：基本在一個(gè)圖中，殘留網(wǎng)絡(luò)指在既有的容量和已具備的流量條件下，網(wǎng)絡(luò)中仍然可以繼續(xù)增大流量的邊所組成的網(wǎng)絡(luò)，在該網(wǎng)絡(luò)中的一條從源點(diǎn)流向匯點(diǎn)的路徑叫做一條增廣路，增廣路算法利用不斷尋找增廣路并在其上對(duì)流量進(jìn)行更新的方法尋找網(wǎng)絡(luò)的最大流。圖的割可以用來(lái)表示對(duì)圖的一個(gè)劃分，將原圖G=(V,E)的頂點(diǎn)集V分為S、T兩部sStTS、T間的最大凈流量為割(S,T)的容量，對(duì)殘留網(wǎng)絡(luò)進(jìn)行廣度優(yōu)先搜索尋找增廣路并對(duì)找到的增廣所經(jīng)過(guò)的邊的流量進(jìn)行更新，找到該路徑上可增加流量最小的一條邊(i,j),對(duì)于該增廣的每條邊，將正向邊的流量增加cap(i,j)-flow(i,j),反向邊的流量減少相同值，反復(fù)執(zhí)行直到找不到增廣路為止，這樣就得到了計(jì)算最大流的基礎(chǔ)的EK算法：對(duì)圖中滿足c(i,j)>f(i,j)的邊進(jìn)行廣度優(yōu)先搜索，并記錄廣搜過(guò)程中最小的c(i,j)-f(i,j)，設(shè)其值為m;若在1中沒(méi)有找到匯點(diǎn)，則算法結(jié)束，若找到匯點(diǎn)，則從匯點(diǎn)開始沿著在廣搜中找到的源點(diǎn)到匯點(diǎn)的路徑反向回到源點(diǎn)，并對(duì)路徑上的每條邊(i,j)執(zhí)行另一種增廣路算法Dinic算法按廣度優(yōu)先搜索對(duì)原圖進(jìn)行分層操作，計(jì)算出每個(gè)頂點(diǎn)1的兩個(gè)頂點(diǎn)間進(jìn)行增廣，使用深度優(yōu)先搜索束，因?yàn)槭褂昧朔謱雍投啻卧鰪V，Dinic的速度要比EK快很多。c(i,j)>f(i,j)id[i]==d[j]-1ISAPDinic算法不同，對(duì)原圖進(jìn)行與匯點(diǎn)最短距離的標(biāo)記，并且在增廣過(guò)程中Dinic1的規(guī)則在殘留網(wǎng)絡(luò)中尋找可增廣邊，找到匯點(diǎn)則進(jìn)行一次增廣，如果在某點(diǎn)處找不到標(biāo)記遞減1初始化流網(wǎng)絡(luò)進(jìn)行一次反向廣度優(yōu)先搜索，找到每個(gè)頂點(diǎn)到匯點(diǎn)的最短距離若在3中找到滿足條件的點(diǎn)：若該點(diǎn)是匯點(diǎn)，則進(jìn)行一次增廣，若該點(diǎn)不是匯點(diǎn)，重復(fù)3，若沒(méi)有找到滿足條件的點(diǎn)，在滿足c(i,j)>f(i,j)的邊中尋找d值最小的，并將該點(diǎn)的d值設(shè)為這個(gè)最小值加1，回到該點(diǎn)的上一個(gè)點(diǎn)，繼續(xù)重復(fù)3;在計(jì)算過(guò)程一般中使用一個(gè)輔助數(shù)組num[]記錄每個(gè)距離標(biāo)號(hào)的頂點(diǎn)數(shù)，比如距離匯45num[4]=5,numnum值為0，則計(jì)算過(guò)程結(jié)束，這個(gè)優(yōu)化被叫做Gap優(yōu)化。解題模板intek(intst,inted,intsrc,inttar)//sted節(jié)點(diǎn)編號(hào)范圍，srctar{intres=0;intpre[N];intmn[N];{{intt=q.front();for(int{if(!fl[i]&&cap[t][i]-{}}if(pre[tar]!=-{{flow[i][pre[i]]-}}}elseres+=mn[tar];}return}Dinic#defineINF#defineMIN(a,b)#defineMAX(a,b)((a)>(b)?(a):(b))#defineN500intcap[N][N];//容量intflow[N][N];//流量intlev[N];//層次boolvis[N];//標(biāo)記//BSF找層次網(wǎng)絡(luò)，一次尋找多條增廣//st最小頂點(diǎn)標(biāo)號(hào)，ed最大頂點(diǎn)標(biāo)號(hào)，src源點(diǎn)標(biāo)號(hào)，tar匯點(diǎn){intfront;//隊(duì)首intrear;//隊(duì)尾{intt=que[rear];for(int{{}}}return}//利用層次網(wǎng)絡(luò)進(jìn)行增廣，每次DFS尋找的是從該節(jié)點(diǎn)出發(fā)進(jìn)行DFS增加的總流//mn表示從源點(diǎn)至該節(jié)點(diǎn)可增廣intdfs(intv,intst,inted,inttar,intfl)//fl{intret=0;if(v==tar||fl==0)returnfl;for(inti=st;i<=ed;i++){{intf=MIN(fl,cap[v][i]-flow[v][i]);//i點(diǎn)向下可用最大流量inttt=dfs(i,st,ed,tar,f);//沿i點(diǎn)向下實(shí)際增廣的流量flow[i][v]-}}return}intdinic(intst,inted,intsrc,int{intret=0;{intr=dfs(src,st,ed,tar,INF);}return}ISAPGAPconstintINF=INT_MAX/3;constintMAXN=20000+5;constintMAXM=200000+5;struct{intu,v;intc;intnext;Edge()Edge(inttu,inttv,inttc,inttn):u(tu),v(tv),c(tc),next(tn)EdgeE[MAXM*intnE,head[MAXN],cnt[MAXN],que[MAXN],d[MAXN],low[MAXN],voidaddEdge(intuintvintcintrc0c正向弧容量，rcE[nE]=Edge(u,v,c,head[u]);head[u]=nE++;E[nE]=Edge(v,u,rc,head[v]);head[v]=nE++;}voidinitNetwork(intnMAXNhead[數(shù)組初始化為-1memset(head,-1,sizeof(head[0])*n);nE=}intmaxflow(intn,intsource,int{int*fr=que,*ta=for(inti=0;i<n;++i)d[i]=n,cnt[i]=0;cnt[n]=n-1,cnt[0]++,d[sink]=0;*ta++=sink;while(fr<ta){intv=for(inti=head[v];i!=-1;i=E[i].next)if(d[E[i].v]==n&&E[i^1].c>0)d[E[i].v]=d[v]+*ta++=}}}intflow=0,u=source,top=0;low[0]=INF;for(inti=0;i<n;++i)cur[i]=head[i];while(d[sourcenquepre數(shù)組，存的是邊int&i=for(;i!=-1;i=E[i].next)if(E[i].c>0&&d[u]==d[E[i].v]+1)low[top+1]=low[top]<E[i].c?low[top]:E[i].c;que[top+1]=i;u=E[i].v;}}if(i!=-1)if(u==sink)intdelta=for(intp=1,i;p<=top;{i=E[i].c-=E[i^1].c+=}}}else

flow+=delta;u=source;low[0]=INF;top=intold_du=d[u];d[u]=n-for(inti=head[u];i!=-1;i=E[i].next)if(E[i].c>0&&d[u]>d[E[i].v])d[u]=}if(d[u]<n)cur[u]=head[u];if(u!=source){u=--}if(cnt[old_du]==0)}}return}經(jīng)典POJ要進(jìn)入有開關(guān)的房間中則需要門是開著的，現(xiàn)在有的房間中有者，同時(shí)有一個(gè)非常重要的房間需要保護(hù)，問(wèn)要保護(hù)那個(gè)房間不被，最少要關(guān)上幾道門。對(duì)于在開關(guān)側(cè)房間的者，無(wú)論關(guān)多少個(gè)門，都無(wú)法他進(jìn)入開關(guān)連接的另一側(cè)房間，對(duì)于在開關(guān)另一側(cè)房間的者，只要關(guān)上這個(gè)開關(guān)，就可以他進(jìn)入有開關(guān)的一側(cè)房間，所以可以以房間為頂點(diǎn)，門為邊，將兩種情況分別連無(wú)窮大的容量與1的容量，另外設(shè)一個(gè)單獨(dú)的源點(diǎn)，將其到每個(gè)有者的房間連無(wú)窮大的邊，求出從源點(diǎn)到保usingnamespacestd;int#defineINF#defineMIN(a,b)#defineMAX(a,b)((a)>(b)?(a):(b))#defineSIZE30intflow[SIZE][SIZE];intcap[SIZE][SIZE];intlev[SIZE];intmn[SIZE];intque[100000];//BSF找層次網(wǎng)絡(luò)，一次尋找多條增廣//st最小頂點(diǎn)標(biāo)號(hào)，ed最大頂點(diǎn)標(biāo)號(hào)，src源點(diǎn)標(biāo)號(hào)，tar匯點(diǎn)boolbfs(intst,inted,intsrc,int{intfront;intrear;{intt=que[rear];for(int{{{}}}}return}//利用層次網(wǎng)絡(luò)進(jìn)行增廣，每次DFS尋找的是從該節(jié)點(diǎn)出發(fā)進(jìn)行DFS增加的總//mn表示從源點(diǎn)至該節(jié)點(diǎn)可增廣intdfs(intv,intst,inted,intsrc,int{intret=0;if(v==tar)returnmn[tar];for(inti=st;i<=ed;i++){{inttt=dfs(i,st,ed,src,tar);flow[i][v]-}}{}return}intdinic(intst,inted,intsrc,int{intret=0;{intr=dfs(src,st,ed,src,tar);}return}int{intt;{for(inti=0;i<m;i++){charch[5];intc;{}for(int{intnum;{}}}intres=dinic(0,m,m,n);elseprintf("PANICROOMBREACH\n");}return}ZOJN<=100）stfloyd或者dijkstradis[s][i]+dis[j][t]+g[i][j]==dis[s][t]dis[s][i],dis[j][t],g[i][j]都不為無(wú)窮大的邊，將其容量設(shè)為1，其他邊容量設(shè)為0，求出st的最大流即得解。usingnamespacestd;#defineINF#defineMIN(a,b)#defineMAX(a,b)((a)>(b)?(a):(b))#defineN500intg[N][N];boolfl[N];intr[N][N];intintintlev[N];boolvis[N];int//BSF找層次網(wǎng)絡(luò)，一次尋找多條增廣//st最小頂點(diǎn)標(biāo)號(hào)，ed最大頂點(diǎn)標(biāo)號(hào)，src源點(diǎn)標(biāo)號(hào)，tar匯點(diǎn)boolbfs(intst,inted,intsrc,int{intfront;intrear;{intt=que[rear];for(int{{}}}return}//利用層次網(wǎng)絡(luò)進(jìn)行增廣，每次DFS尋找的是從該節(jié)點(diǎn)出發(fā)進(jìn)行DFS增加的總//mn表示從源點(diǎn)至該節(jié)點(diǎn)可增廣intdfs(intv,intst,inted,inttar,int{intret=0;if(v==tar||fl==0)returnfl;for(inti=st;i<=ed;i++){{intf=MIN(fl,cap[v][i]-flow[v][i]);inttt=dfs(i,st,ed,tar,f);flow[i][v]-}}return}intdinic(intst,inted,intsrc,int{intwhile(bfs(st,ed,src,tar))//存在可增廣{intr=dfs(src,st,ed,tar,INF);}return}int{intn;{for(int{for(int{if(g[i][j]==-}}intsrc,tar;{}for(int{for(int{for(int{{}}}}for(int{for(int{{}{}}}intres=dinic(1,n,src,tar);}return}編寫：校核：基本用SPFA最短路算法和EK最大流算法結(jié)合的方法求解最小費(fèi)用最大流問(wèn)題。模板#defineINF#defineMIN(a,b)intmat[55][55];intn,k;inthead[5005];structArc{intnext_arc;intpoint;intadj;intcost;intcap;structArcintpre[5005];intdis[5005];boolfl[5005];intmax_flow;intintvoidadd(intu,intv,intcst,int{ }voidcost_flow(intsrc,int{{{intu=q.front();{{{}}}}intmin=INF;{}{}}}經(jīng)典POJ有一個(gè)N*N的矩陣，每個(gè)位置有一個(gè)非負(fù)整數(shù)，從左上角到右下角走，經(jīng)過(guò)每個(gè)位sum中，sum0Ksum的1相連的，則從一個(gè)位置的兩個(gè)頂點(diǎn)分別到另一個(gè)位置的兩個(gè)頂點(diǎn)建立四條邊，容量為無(wú)012K費(fèi)用為0的邊，求出最大費(fèi)用即可。int{{for(inti=1;i<=n;i++){for(int{}}for(int{for(int{intp3=(i-1)*n+j;{intp1=(i-1)*n+j;intp2=i*n+j;}{intp1=(i-1)*n+j;}}}printf("%d\n",-}return}王桂平.《圖論算法理論、實(shí)現(xiàn)及應(yīng)用》2011年編寫：校核：基本上下界最大流對(duì)普通的最大流問(wèn)題附加了一個(gè)流量上界和下界，求在每條邊的流量不超過(guò)此上、下界的情況下可得的最大或最小流量，普通的最大流問(wèn)題可以看成是下界為0，上界是容量的最大流問(wèn)題。VsVt如果在該最大流中，所有從Vs發(fā)出的弧都滿載，則原網(wǎng)絡(luò)存在滿足上下界條件的流，否要求解滿足流量上下界的流中的最大流，在利用上述方法得到可行流之后的基礎(chǔ)上運(yùn)行最大流算法，并在最大流算法中注意保證每條弧的流量在減少之后不能少于流量下界，即減少的流量不能多于該弧的流量與其下界之差，如此即可得到滿足條件的最大流。反之在求滿足流量上下界的最小流時(shí)，首先找到可行流，然后在可行流基礎(chǔ)上，在原圖中以匯點(diǎn)為源點(diǎn)，源點(diǎn)為匯點(diǎn)，即源匯點(diǎn)交換再將可行流放大，如果匯點(diǎn)到源點(diǎn)有路徑并且該路徑上的弧在可行流中都并沒(méi)有達(dá)到上界，那么該過(guò)程就會(huì)將匯點(diǎn)到源點(diǎn)的流放大，相應(yīng)的源點(diǎn)到匯點(diǎn)的流應(yīng)會(huì)減少，將該流擴(kuò)大為最大流，此時(shí)源點(diǎn)到匯點(diǎn)的流量即為最小流。經(jīng)典POJ有類型，流量上下界為該類型費(fèi)用和，對(duì)每個(gè)約束條件中的r,q按相應(yīng)的約束條件修改相應(yīng)弧的流量上下辦，注意重復(fù)輸入，上界應(yīng)取最小的，下界應(yīng)取最大的，因題目specialint{intt;boolfirst=1;{for(inti=0;i<m;i++)//1為源點(diǎn)，此處為輸入每行的和，第i行對(duì)應(yīng)頂點(diǎn){intnu;}for(inti=0;i<n;i++)//輸入n列的和以m+n+2{intnu;}intc;for(int{intr,q,v;charch;scanf("%d%d%c%d",&r,&q,&ch,&v);{{}else{g2[r+1][q+m+1]=MIN(g2[r+1][q+m+1],v-}{}}{{{for(int{for(int{}}}else{for(int{for(int{g2[i1+2][m+2+j1]=MIN(g2[i1+2][m+2+j1],v-}}}{for(int{for(int{}}}}else{{for(int{}}else{for(int{g2[i+2][m+q+1]=MIN(g2[i+2][m+q+1],v-}}{for(int{}}}{{for(int{}}else{for(int{g2[r+1][m+2+i]=MIN(g2[r+1][m+2+i],v-}}{for(int{}}}}}for(int{for(int{cap[i+2][j+m+2]=g2[i+2][j+m+2]-g1[i+2][j+m+2];//修改每條邊的}}for(int{intfor(int{}cap[i][m+n+3]=num;//頂點(diǎn)i到附加匯點(diǎn)的容量為i流出的下for(int{}}dinic(0,m+n+3,0,m+n+3);//該處直接調(diào)用上面的最大流函數(shù)即可，以0為附加源點(diǎn)，m+n+3if(!first)//判斷是否第一組測(cè)試數(shù)據(jù){}intjud=1;//判斷是否得到了可行流for(inti=1;i<=m+n+3;i++){{}}{}for(int{for(int{if(j>0)printf("");}}}return}編寫：校核：基本1GV,E)V中取盡可能少的點(diǎn)組成一個(gè)VV`G的一個(gè)支配uV`V`V`中V`V`G的所有支配集中頂點(diǎn)2GV,E)V中取盡可能少的點(diǎn)組成一個(gè)EV`G的一個(gè)頂點(diǎn)覆蓋，則對(duì)于圖中任意一條邊（u,v）,uV`vV`V`中除去任何元后V`不再是頂點(diǎn)覆蓋，則V`是極小頂點(diǎn)覆蓋。稱G的所有頂點(diǎn)覆蓋中頂點(diǎn)個(gè)數(shù)3G（V,E）V中取盡量多的點(diǎn)組成一個(gè)集合，使得這些點(diǎn)之間沒(méi)有邊相連。也就是說(shuō)設(shè)V`是圖G的一個(gè)獨(dú)立集，則對(duì)于圖中任意一條邊（u,v）,uvV`uvV`V`V`V`V`G的所有頂點(diǎn)獨(dú)立集G來(lái)說(shuō)，最小支配集、最小點(diǎn)覆蓋與最大獨(dú)立集問(wèn)題不存在多項(xiàng)式時(shí)間的G是一棵樹，求這三種特殊的集合倒是十分容易。目前有兩種解法，一種基于貪心思想，另一種基于樹形動(dòng)態(tài)規(guī)劃思想，這兩種算法都可以解決上面的3個(gè)問(wèn)(1)這里注意到貪心的策略中貪心的順序非常重要，按照深度優(yōu)先遍歷得到遍歷序列的反方向進(jìn)行貪心，可以保證對(duì)于每個(gè)點(diǎn)來(lái)說(shuō)，當(dāng)其子樹都被處理過(guò)后才會(huì)輪到該節(jié)點(diǎn)的處理，保證了貪心的正確性。1號(hào)點(diǎn)深度優(yōu)先搜索整棵樹，求出每個(gè)點(diǎn)在深度優(yōu)先遍歷序列中的編號(hào)和每②按照深度優(yōu)先序列的反向序列檢查，如果當(dāng)前點(diǎn)既不屬于支配集也不與支配集點(diǎn)的個(gè)數(shù)加1。標(biāo)記當(dāng)前節(jié)點(diǎn)、當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的父節(jié)相連(當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的父節(jié)點(diǎn))最小點(diǎn)覆蓋與最大獨(dú)立集與上面的做法相似，都需要先求得深度優(yōu)先遍歷序列，按照反方向貪心以保證貪心的正確性。對(duì)于最小點(diǎn)覆蓋來(lái)說(shuō)，貪心的策略是，如果當(dāng)前點(diǎn)和當(dāng)前點(diǎn)的父節(jié)點(diǎn)都不屬于覆蓋集合，則將父節(jié)點(diǎn)加入到頂點(diǎn)覆蓋集合，并標(biāo)記當(dāng)前節(jié)點(diǎn)和其父節(jié)點(diǎn)都被覆蓋。對(duì)于最大獨(dú)立集來(lái)說(shuō)，貪心策略是如果當(dāng)前節(jié)點(diǎn)沒(méi)有被覆蓋，則將當(dāng)前節(jié)點(diǎn)加入獨(dú)立集，并標(biāo)記當(dāng)前節(jié)點(diǎn)和其父節(jié)點(diǎn)都被覆蓋。其自身，所以三種問(wèn)題對(duì)于根節(jié)點(diǎn)的處理也不同。對(duì)于最小支配集和最大獨(dú)立集，需要檢查根節(jié)點(diǎn)是否滿足貪心條件，但是對(duì)于最小點(diǎn)覆蓋不可以檢查根節(jié)DFS（，newpos[i]i個(gè)點(diǎn)是哪個(gè)點(diǎn)，now表示當(dāng)前深度優(yōu)先遍歷序列已經(jīng)有多少個(gè)點(diǎn)了。Select[]用于深度優(yōu)先遍歷的判重，p[i]表示點(diǎn)i的父節(jié)點(diǎn)的編號(hào)。對(duì)于greedy（）,s[i]如果為true,表示第i個(gè)點(diǎn)被覆蓋。Set[i]表示點(diǎn)i屬于要求的點(diǎn)集。（1）雜。還是以最小支配集為例，為了保證動(dòng)態(tài)規(guī)劃的正確性，對(duì)于每個(gè)點(diǎn)設(shè)計(jì)了三種狀dp[i][0]:ii為根的子樹都被覆蓋了的情況下支dp[i][1]:iiidp[i][2]:iii沒(méi)被子節(jié)點(diǎn)覆蓋的那么對(duì)于第一種狀態(tài)，dp[i][0]等于每個(gè)兒子節(jié)點(diǎn)的3種狀態(tài)（其兒子是否被覆蓋沒(méi)有關(guān)系）的最小值之和加1，即只要每個(gè)以i的兒子為根的子樹都被覆蓋，再加上當(dāng)前點(diǎn)i，所需要的最少的點(diǎn)的個(gè)數(shù)，方程如下：dp[i][0]1+∑min(dp[u][0dp[u][1],dp[u][2])（ui的兒子idp[i][1]=INF；否則，需要保證它的每個(gè)以i的兒子為根的子樹都被覆蓋，那么要取每個(gè)兒子節(jié)點(diǎn)的前兩種狀態(tài)的最小值之和，因?yàn)榇藭r(shí)i點(diǎn)不屬于支配集，不能支配其子節(jié)點(diǎn)，所以子節(jié)點(diǎn)必須已經(jīng)被分配，與狀態(tài)的定義，需要重新選擇點(diǎn)i的第一個(gè)兒子的狀態(tài)為第一種狀態(tài)，這時(shí)取花費(fèi)最少的一個(gè)點(diǎn)，即取min（dp[u][0]-dp[u][1]）的兒子節(jié)點(diǎn)u，強(qiáng)其第一種狀態(tài)，其他的兒if(i沒(méi)有子節(jié)點(diǎn)dp[i][1]elsedp[i][1]=∑min(dp[u][0],dp[u][1])inc（ui的兒子）其中對(duì)于inc有：if上面的式子中∑min(dp[u][0],dp[u][1])中包含某dp[u][0])inc0；elseinc=min（dp[u][0]–dp[u][1]）(ui的兒子)對(duì)于第三種狀態(tài)，iiiiii的第三種狀態(tài)只與其兒子dp[i][2]= (ui的兒子①dp[i][0]ii為根的子樹中所連接的邊都被覆蓋的情②dp[i][1]ii為根的子樹中所連接的邊都被覆蓋的情dp[i][0]1+min(dp[u][0], (ui的兒子對(duì)于第二種狀態(tài)dp[i][1],要求所有與i相連的邊都被覆蓋，但是iii的第二種狀態(tài)與所有子節(jié)點(diǎn)的dp[i][1]=dp[u][0]ui的兒子對(duì)于第一種狀態(tài)dp[i][0]，由于i點(diǎn)屬于獨(dú)立集，它的字節(jié)點(diǎn)都不能屬于獨(dú)立集，所以對(duì)于點(diǎn)i的第一種狀態(tài)，只與子節(jié)點(diǎn)的第二種狀態(tài)有關(guān)，等于其所有子節(jié)點(diǎn)的第二種狀態(tài)的值的和加1，方程如下：dp[i][0]1+∑dp[u][1ui的兒子節(jié)點(diǎn)對(duì)于第二種狀態(tài)dp[i][1],由于點(diǎn)i不屬于獨(dú)立集，所以點(diǎn)i的子節(jié)點(diǎn)可以屬于獨(dú)立dp[i][1]=∑max(dp[u][0],模板intboolselect[maxn];intnewpos[maxn];intnow;intn,voidDFS(int{newpos[now++]=x;intk;for(k=head[x];k!=-1;{if{select[edge[k].to]=true;p[edge[k].to]=x;}}}int{bools[maxn]=boolset[maxn]={0};intans=0;intfor(i=n-1;i>=0;i--{intt=newpos[i];if(!s[t]){if{set[p[t]]=true;}s[t]=true;s[p[t]]=true;s[p[p[t]]]=}}return}int{bools[maxn]={0};boolset[maxn]={0};intans=0;intfor(i=n-1;i>=1;i--{intt=if(!s[t]&&{set[p[t]]=true;s[t]=true;s[p[t]]=true;}}return}int{bools[maxn]={0};boolset[maxn]={0};intans=0;intfor(i=n-1;i>=0;i--{intt=newpos[i];if(!s[t]){set[t]=true;s[t]=true;s[p[t]]=true;}}return}int{now=0;select[1]=true;p[1]=1;}在下面的代碼中，u表示當(dāng)前正在處理的節(jié)點(diǎn)，pu節(jié)點(diǎn)的父節(jié)點(diǎn)。voidDP(intu,int{dp[u][2]=dp[u][0]=bools=intsum=0,inc=INF;intk;for(k=head[u];k!=-1;{intto=edge[k].to;if(to==p)DP(to,dp[u][0]+=min(dp[to][0],min(dp[0][1],dp[to][2]));if(dp[to][0]<=dp[to][1]){sum+=dp[to][0];s=true;}{sum+=}if(dp[to][1]!=INF&&dp[u][2]+=dp[to][1];elsedp[u][2]=INF;}if(inc==INF&&!s)dp[u][1]=INF;{dp[u][1]=sum;if(!s)dp[u][1]+=inc;}}void{dp[u][0]=dp[u][1]=intk,for(k=head[u];k!=-1;{to=edge[k].to;if(to==p)dp[u][0]+=min(dp[to][0],dp[to][1]);dp[u][1]+=dp[to][0];}}void{dp[u][0]=dp[u][1]=intk,for(k=head[u];k!=-1;{to=edge[k].to;if(to==p)DP(to,u);dp[u][0]+=dp[u][1]+=max(dp[to][0],}}dp[root][0] 《圖論算法理論、實(shí)現(xiàn)及應(yīng)用》王桂平、王衍任嘉辰 2011年1月第編寫：校核：基本G=<V,E>X、YX∪Y=VX∩Y=Φ，并且e={x，y}x∈X，y∈YG為一個(gè)二分圖(bipartitegraph)。常用<X,E,Y>XxYye∈Eex,y},G為完全二分圖(completebipartitegraph)。當(dāng)|X|=m，|Y|=nGKm,n。匹配：設(shè)G=<V,E>為二分圖，如果M?E，并且M完全匹配:X(Y)MMM既X-完全匹配又是Y-完全匹配，則稱MG的完全匹配。注意:最大匹配總是存在但未必唯一；X(Y)-完全匹G的完全匹配必定是最大的，G=<V,E>為二分圖，MG的一個(gè)匹配M中邊的端點(diǎn)稱為M-頂點(diǎn)，其它頂點(diǎn)稱為非M-增廣路徑:除了起點(diǎn)和終點(diǎn)兩個(gè)頂點(diǎn)為非M-頂點(diǎn)，其他路徑上所有的點(diǎn)都是M=頂 圖 圖圖（1）中列出了一個(gè)匹配：[1,Y]。圖（2）是在這個(gè)匹配的基礎(chǔ)上的兩個(gè)增廣路徑： Y1和 Y3間點(diǎn)Y2、X1都是M-頂點(diǎn)。邊{X2,Y2},{X1,Y1}為非匹配邊，而邊{Y2,X1}為匹配邊，滿足匹配邊與非匹配邊交廣路徑中的所有第偶數(shù)條邊從原匹配中刪除（這個(gè)操作稱為增廣路徑的取反，則新的匹配數(shù)就比原匹配數(shù)增加了1個(gè)。解題while找while找得到增廣do搜索增廣路徑的方法是DFS，寫一個(gè)遞歸的函數(shù)。當(dāng)然也可以用BFS。至此，理論基礎(chǔ)部份講A出發(fā)，沒(méi)有找到增廣路徑，那么無(wú)論再?gòu)膭e的點(diǎn)出發(fā)找到多少增廣路徑來(lái)改變現(xiàn)在的匹配，從A出發(fā)都找不到增廣路徑。模板#include<iostream>#include<string.h>usingnamespaceintn,k;//n矩陣規(guī)格，k星體數(shù)量intV1,V2;//boolgrid[501][501];//數(shù)據(jù)方式：可達(dá)矩陣bool //記錄V2的點(diǎn)每個(gè)點(diǎn)是否已被搜索int //V2中的點(diǎn)yV1xintm;//最大匹配數(shù)booldfs(intx){for(intif(grid[x][y&&!vis[y])//x到y(tǒng)相鄰(有邊y{ //標(biāo)記節(jié)點(diǎn)y已被 link[y]=x那么可以更新匹配M'(用M替代M')returntrue;//返回匹配成功的標(biāo)志}}returnfalse;//繼續(xù)查找V1下一個(gè)x}void{for(int{if(dfs(x))//從V1中的節(jié)點(diǎn)x開始尋找增廣路}}int{intx,y; for(inti=1;i<=k;i++){grid[x][y]=true;//}return}經(jīng)典題目出處HDU2063題目描述:RPGgirls今天和大家一起去游樂(lè)場(chǎng)玩，終于可以坐上夢(mèng)寐以求的過(guò)山車 找個(gè)個(gè)男生做partner和她同坐。但是，每個(gè)都有各自的想法，舉個(gè)例子把，Rabbit只XHDPQKpartner，GrasslinleLLpartner，PrincessSnow愿意partner?？紤]到經(jīng)費(fèi)問(wèn)題，bosspartner的人去坐過(guò)山車，其他的人，嘿嘿，就站在下面看著吧。聰明的Acmer，你可以幫忙算算最多有多少對(duì)分析 #defineclr(x)memset(x,0,sizeof(x))boolg[505][505];boolv[505];intl[505];intn,m;intfind(int{inti;{{v[i]=1;/*男生k與i配對(duì)(i未與別的男生配對(duì)*i與別的男生(l[i])配對(duì)了*但從與i配對(duì)的男生開始找,可以找到另外一個(gè)可以匹配的*/{return1;}}}return}int{inti,k,p,q,tot;{clr(g);clr(l);{}for(i=1;i<=n;i++)//每個(gè)男的{}}return}題目出處POJ2771Guardianof題目描述:n個(gè)人，和四個(gè)條件，兩個(gè)人只要滿足其中任意一個(gè)條件就不能分析:=-#defineclr(x)memset(x,0,sizeof(x))structnode{intinthead[505];inttot;voidadd(ints,intu{}struct{inth;charx[3];charmu[103];charintlink[505];intv[505];intfind(intx){inti,k;{{{return1;}}}return}intabs(int{returnx>0?x:-x;}intok(pera,perb){return0;return0;return0;return}int{int{{}printf("%d\n",n-}return}2012 2012

《圖論算法理論、實(shí)現(xiàn)及應(yīng)用》王桂平、2011年1月第一編寫：校核：基本下圖中，子圖{1,2,3,4}1,2,3,4兩兩可達(dá)。{5},{6}也分別 直接根據(jù)定義，向遍歷取交集的方法求強(qiáng)連通分量，時(shí)間復(fù)雜度為O(N^2+M)。KosarajuTarjanO(N+M)。本章將介紹的是Tarjan算法，關(guān)于Kosaraju算法可以查閱相關(guān)資料。解題Tarjan算法是基于對(duì)圖深度優(yōu)先搜索的算法，每個(gè)強(qiáng)連通分量為搜索樹中的一棵子DFN(u)為節(jié)u搜索的次序編號(hào)(時(shí)間戳)，Low(u)uu的能夠追溯到的最早的棧點(diǎn)的次序號(hào)。由定義可以得出{}當(dāng)DFN(u)=Low(u)時(shí)，以u(píng)為根的搜索 { foreach(uvin if(visnot //如果節(jié)點(diǎn)v未被 Low[u]=min(Low[u],elseifvin Low[u]=min(Low[u],if(DFN[u v printvuntil(u==v)}從節(jié)點(diǎn)1開始DFS，把遍歷到的節(jié)點(diǎn)加入棧中。搜索到節(jié)點(diǎn)u=6時(shí)，DFN[6]=LOW[6]，找到了一個(gè)強(qiáng)連通分量。退棧到u=v為止，{6}為一個(gè)強(qiáng)連通分量31DFN: 3165DFN:46561 DFN:3LOW:361DFN:434441有后向邊，節(jié)1LOW[4]=1。節(jié)6已經(jīng)出棧，(4,6)是橫叉邊3，(3,4)為樹枝邊，所以LOW[3]=LOW[4]=1。 DFN:2 DFN:3DFN:5 DFN:4繼續(xù)回到節(jié)點(diǎn)1，最后訪問(wèn)節(jié)點(diǎn)2。邊(2,4)，4還在棧中，所以LOW[2]=DFN[4]=5。返回1后，發(fā)現(xiàn)DFN[1]=LOW[1]，把棧點(diǎn)全部取出，組成一個(gè)DFN:1 DFN:2 11352461243DFN:6 DFN:5 至此，算法結(jié)束。經(jīng)過(guò)該算法，求出了圖中全部的三個(gè)強(qiáng)連通分量{1,3,4,2},{5},{6}?？梢园l(fā)現(xiàn)，運(yùn)行arjan算法的過(guò)程中，每個(gè)頂點(diǎn)都被了一次，且只進(jìn)出了一次堆模板voidtarjan(int{intj;{j=e-if{if}elseif(instack[j]&&DFN[j]<LOW[i])}if{{ }while}}void{intfor(i=1;i<=N;i++)if}經(jīng)典題目出處HDU1269題目描述:給一個(gè)有nm條有向邊，問(wèn)這個(gè)圖中是否任意分析:任意兩個(gè)點(diǎn)能夠互達(dá)，即要求圖的強(qiáng)連通分量的個(gè)數(shù)為一，求出圖的強(qiáng)連通子圖#defineclr(x)memset(x,0,sizeof(x))constintmaxn=100010;structnode{intto;intnext;inthead[100010];inttot;intvoidadd(ints,int{q[tot].to=u;q[tot].next=head[s];head[s]=tot++;}intdfn[maxn];intlow[maxn];intstack[maxn];intti,sn,top;boolinstack[maxn];voidtarjan(intu){dfn[u]=low[u]=++ti;//取時(shí)間戳stack[++top]=u; //當(dāng)前節(jié)點(diǎn)入棧instack[u]=true;intk,for(i=head[u];i;