1、圖論-普及,洛谷 - icy 2018-2,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 1,引子,冒泡排序，選擇排序，插入排序，快速排序，堆排序，歸并排序，希爾排序，桶排序，基數(shù)排序新年幫您排憂(yōu)解難。 有向圖，無(wú)向圖，有環(huán)圖，無(wú)環(huán)圖，完全圖，稠密圖，稀疏圖，拓?fù)鋱D祝您新年宏圖大展。 最長(zhǎng)路，最短路，單源路徑，所有節(jié)點(diǎn)對(duì)路徑祝您新年路路通暢。 二叉樹(shù)，紅黑樹(shù)，van Emde Boas樹(shù)，最小生成樹(shù)祝您新年好運(yùn)枝繁葉茂。 最大流，網(wǎng)絡(luò)流，標(biāo)準(zhǔn)輸入流，標(biāo)準(zhǔn)輸出流，文件輸入流，文件輸出流祝您新年順順流流。 線(xiàn)性動(dòng)規(guī)，區(qū)間動(dòng)規(guī)，坐標(biāo)動(dòng)規(guī)，背包動(dòng)規(guī)，樹(shù)型動(dòng)歸為您的新年規(guī)劃精彩。 散列表，哈希表，鄰接表，雙向

2、鏈表，循環(huán)鏈表幫您在新年表達(dá)喜悅。 O(1), O(log n), O(n), O(nlog n), O(n2), O(n3), O(2n), O(n!)祝您新年漸進(jìn)步步高。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 2,圖論目錄for普及,圖是什么 圖論簡(jiǎn)介 圖的存儲(chǔ) 圖的存儲(chǔ)與遍歷 鄰接矩陣 鄰接表 圖的遍歷 圖的最短路徑 BFS灌水法 Floyd算法 Dijkstra算法 Spfa算法 圖的最小生成樹(shù)(MST) Prim算法 Kluskal算法 簡(jiǎn)單聯(lián)通塊及 拓?fù)渑判蚝虳AG 樹(shù) 樹(shù)的相關(guān)知識(shí) 樹(shù)上節(jié)點(diǎn)最近公共祖先（LCA）,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 3,圖論目錄for全體o

3、ier,圖是什么 圖論簡(jiǎn)介 圖的存儲(chǔ) 圖的存儲(chǔ)與遍歷 鄰接矩陣 鄰接表 圖的遍歷 圖的最短路徑 BFS灌水法 Floyd算法 Dijkstra算法 Spfa算法 Bellman-ford算法 *Johnson算法 *A-Star算法 圖的最小生成樹(shù)(MST) Prim算法 Kluskal算法 *聯(lián)通塊及Tarjan強(qiáng)連通 樹(shù) 樹(shù)的相關(guān)知識(shí) *最近公共祖先lca 樹(shù)的直徑 *樹(shù)鏈剖分 *差分約束 *二分圖匹配 *二叉樹(shù)二叉堆 ,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 4,圖,下面的就是一張圖（霧） 圖片出自國(guó)產(chǎn)動(dòng)漫鎮(zhèn)魂街 這個(gè)只能算得上圖片，不是圖，不屬于oi圖論范圍。,洛谷網(wǎng)校冬令營(yíng) 2018

4、.2,Page 5,圖,圖論Graph Theory是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象，研究頂點(diǎn)和邊組成的圖形的數(shù)學(xué)理論和方法 。 圖論發(fā)展到我們現(xiàn)在，已經(jīng)擁有一個(gè)很龐大的體系。圖論成為了信息學(xué)的一大專(zhuān)題，也出現(xiàn)過(guò)很多的難題。 如今我們學(xué)習(xí)圖論要從最基礎(chǔ)的開(kāi)始學(xué)起，一步一步吃透圖論，在將來(lái)的信息學(xué)競(jìng)賽拿分。 這才是真正oi中的圖。 如你所見(jiàn)，圖由點(diǎn)（我們放大為 圓圈）和線(xiàn)組成（或者帶箭頭的 線(xiàn)段）。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 6,圖的相關(guān)定義術(shù)語(yǔ),有向圖：圖中存在有方向邊的圖。邊用表示由u到v的有向邊，不等同于。 無(wú)向圖：圖中不存在有方向邊的圖。邊用(u,v)表示由u到v的邊，等

5、同于(v,u)。 度：與此點(diǎn)相連邊的數(shù)量。 入度：終點(diǎn)為此點(diǎn)的邊的數(shù)量。出度正相反。 子圖：從原圖中選出若干節(jié)點(diǎn)，其中兩兩點(diǎn)之間關(guān)系不變的圖，叫做原圖的子圖。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 7,樹(shù)的相關(guān)定義術(shù)語(yǔ),樹(shù)是由n (n =0)個(gè)結(jié)點(diǎn)組成的有限集合。0個(gè)節(jié)點(diǎn)的叫做空樹(shù)，一般不研究。 結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)； 樹(shù)的度：樹(shù)的所有結(jié)點(diǎn)中最大的度數(shù)； 葉結(jié)點(diǎn)（Leaf）：度為0的結(jié)點(diǎn)； 父結(jié)點(diǎn)（Parent）：有子樹(shù)的結(jié)點(diǎn)是其子樹(shù)的根節(jié)點(diǎn)的父結(jié)點(diǎn)； 子結(jié)點(diǎn)/孩子結(jié)點(diǎn)（Child）：若A結(jié)點(diǎn)是B結(jié)點(diǎn)的父結(jié)點(diǎn)，則稱(chēng)B結(jié)點(diǎn)是A結(jié)點(diǎn)的子結(jié)點(diǎn)； 兄弟結(jié)點(diǎn)（Sibling）：具有

6、同一個(gè)父結(jié)點(diǎn)的各結(jié)點(diǎn)彼此是兄弟結(jié)點(diǎn)；,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 8,樹(shù)的相關(guān)定義術(shù)語(yǔ),路徑和路徑長(zhǎng)度：從結(jié)點(diǎn)node1到nodek的路徑為一個(gè)結(jié)點(diǎn)序列node1，node2，.，nodek。nodei是nodei+1的父結(jié)點(diǎn)。路徑所包含邊的個(gè)數(shù)為路徑的長(zhǎng)度； 祖先結(jié)點(diǎn)（Ancestor）：沿樹(shù)根到某一結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)都是這個(gè)結(jié)點(diǎn)的祖先結(jié)點(diǎn)； 子孫結(jié)點(diǎn)（Descendant）：某一結(jié)點(diǎn)的子樹(shù)中的所有結(jié)點(diǎn)是這個(gè)結(jié)點(diǎn)的子孫； 結(jié)點(diǎn)的層次（Level）：規(guī)定根結(jié)點(diǎn)在1層，其他任一結(jié)點(diǎn)的層數(shù)是其父結(jié)點(diǎn)的層數(shù)加1； 樹(shù)的深度（Depth）：樹(shù)中所有結(jié)點(diǎn)中的最大層次是這棵樹(shù)的深度； 有序樹(shù)

7、和無(wú)序樹(shù)：若結(jié)點(diǎn)的子樹(shù)有次序排列，且先后次序不能互換，這樣的樹(shù)稱(chēng)為有序樹(shù)，反之為無(wú)序樹(shù)。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 9,圖論與oi,Noip2013 提高 貨車(chē)運(yùn)輸 P1967 Noip2013 普及 車(chē)站分級(jí) P1983 Noip2014 提高 聯(lián)合權(quán)值 P1351 Noip2014 普及 尋找道路 P2296 Noip2015 提高 信息傳遞 P2661 Noip2015 提高 運(yùn)輸計(jì)劃 P2680 Noip2016 提高 天天愛(ài)跑步 P1600 Noip2017 提高 逛公園 P3953 Noip2018 ？,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 10,什么是圖？,圖由點(diǎn)

8、和邊組成。根據(jù)邊是否有方向，可分為有向圖、無(wú)向圖。樹(shù)是特殊的無(wú)向圖。 每條邊可以有一個(gè)長(zhǎng)度，當(dāng)然也可以沒(méi)有（默認(rèn)為1）。 圖論題面中頂點(diǎn)的個(gè)數(shù)通常用 n 表示，邊的數(shù)量通常用 m 表示，數(shù)據(jù)范圍一般不對(duì)n, m進(jìn)行解釋。 一般圖論題n, m數(shù)量級(jí)為1e5（aeb為科學(xué)計(jì)數(shù)法，意思為a 10 。,有向圖,無(wú)向圖,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 11,圖的存儲(chǔ)-鄰接矩陣,我們選擇用“鄰接矩陣”表格的方式存儲(chǔ)一個(gè)圖。 存儲(chǔ)規(guī)則：若a能到達(dá)b，則此表格第a行第b列的值就是a到b的距離（或1），無(wú)法訪(fǎng)問(wèn)為-1或正無(wú)窮。 特別的，自己到自己的距離為0。,有向圖,無(wú)向圖,洛谷網(wǎng)校冬令營(yíng) 2018.2

9、,Page 12,圖的存儲(chǔ)-鄰接矩陣,我們選擇用“鄰接矩陣”表格的方式存儲(chǔ)一個(gè)圖。 存儲(chǔ)規(guī)則：若a能到達(dá)b，則此表格第a行第b列的值就是a到b的距離（或1），無(wú)法訪(fǎng)問(wèn)為-1或正無(wú)窮。 特別的，自己到自己的距離為0。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 13,圖的存儲(chǔ)-鄰接表,鄰接表（鏈?zhǔn)角跋蛐牵┐鎯?chǔ)圖比鄰接矩陣更加高效。 鄰接表由點(diǎn)表（由點(diǎn)構(gòu)成的表）（上）和邊表（由邊構(gòu)成的表）（下）組成。 Head數(shù)組存儲(chǔ)的是以該點(diǎn)為起點(diǎn)（按照加入時(shí)間順序）最后加入的一條邊。 邊表from數(shù)組實(shí)際操作沒(méi)有用處，不過(guò)在查錯(cuò)環(huán)節(jié) 還是有用的。 Next數(shù)組是以該邊起始點(diǎn)為起點(diǎn)的上一條邊（按照 加入時(shí)間順序）,

10、洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 14,樹(shù),什么是樹(shù)??？,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 15,樹(shù),什么是樹(shù)??？ 樹(shù)是一個(gè)特殊的圖罷了，沒(méi)啥了不起的。 特殊在這個(gè)n節(jié)點(diǎn)的圖里，有n-1條連接圖的邊，把這些點(diǎn)連接起來(lái)。恰好這些點(diǎn)可以聯(lián)通。 樹(shù)的一些相關(guān)操作 樹(shù)的重心和直徑 倍增LCA（聽(tīng)說(shuō)提高講了那就算了） ,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 16,樹(shù)的存儲(chǔ)方式,父親節(jié)點(diǎn)表示法 兒子節(jié)點(diǎn)表示法 無(wú)向圖表示 左兒子右兄弟 樹(shù)轉(zhuǎn)二叉樹(shù),1,2,1,6,8,7,3,4,5,2,3,6,4,5,7,8,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 17,圖的遍歷,深度優(yōu)先搜索 詳見(jiàn)day5

11、搜索，此處不多講述。 附深度優(yōu)先搜索動(dòng)畫(huà)。,1,3,2,1,5,4,2,3,4,5,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 18,圖的遍歷,廣度優(yōu)先搜索 詳見(jiàn)day5搜索，此處不多講述。 附廣度優(yōu)先搜索動(dòng)畫(huà)。,1,3,2,1,5,4,2,3,4,5,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 19,BFS灌水法,usaco火情蔓延 一個(gè)R*C的方格圖，時(shí)刻0時(shí)某些方格自燃，每秒鐘向四個(gè)方向蔓延，問(wèn)需要多少時(shí)間才使得整個(gè)方格圖都在燃燒。 如圖 由一個(gè)點(diǎn)向四周放射狀發(fā)出，這就是bfs搜索的一種形式。詳見(jiàn)day5 zcysky老師的搜索課。 提示，bfs在圖論一般只適用于相鄰兩點(diǎn)之間距離為1的圖。,洛谷

12、網(wǎng)校冬令營(yíng) 2018.2,Page 20,圖的最短路算法-Floyd,傳遞閉包 傳遞閉包和差分約束是一回事嗎？ 當(dāng)a能到達(dá)b，b能到達(dá)c，則a可以到達(dá)c。 當(dāng)a到b的距離為dis1，b到c的距離為dis2，則至少存在路徑使a到c的距離為dis1+dis2。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 21,圖的最短路算法-Floyd,Floyd 算法是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或無(wú)向圖或負(fù)權(quán)（但不可存在負(fù)權(quán)回路)的最短路徑問(wèn)題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 22,圖的最短路算法-Floyd,初始化： 1. 不可以直接到達(dá)的d

13、is設(shè)為正無(wú)窮(oo)。 2. 自己到自己的距離為0。 3. 題目給定的邊的disij直接賦值為該邊長(zhǎng)度。雙向邊需要disij和disji均賦值為邊長(zhǎng)。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 23,圖的最短路算法-Floyd,Floyd算法使用的思想是： 枚舉中轉(zhuǎn)節(jié)點(diǎn)。 檢查由S點(diǎn)經(jīng)過(guò)此點(diǎn)到T點(diǎn)的路徑是否比原先優(yōu)。 更新由S點(diǎn)到T點(diǎn)的最短距離。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 24,圖的最短路算法-Floyd,注：在oi中，由于正無(wú)窮在代碼里難以表示，我們常將oo或inf定義為足夠大的數(shù)字(0 x3f3f3f3f等)來(lái)表示正無(wú)窮。,5 K=1,5 K=1,2 K=1,7 K=1,14

14、 K=2,13 K=2,12 K=2,7 K=2,8 K=2,8 K=2,10 K=3,11 K=3,9 K=5,10 K=5,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 25,圖的最短路算法-Floyd,Q：為什么要先枚舉K啊 A：這樣便過(guò)早的把i到j(luò)的最短路徑確定下來(lái)了，而當(dāng)后面存在更短的路徑時(shí)，已經(jīng)不再會(huì)更新了。 假如我們求A到B的最短距離。 在內(nèi)層枚舉k：只有A-B唯一一條路線(xiàn)（因?yàn)樵蹅冎荒苊杜e一個(gè)中轉(zhuǎn)點(diǎn)） 在外層枚舉k：可以經(jīng)過(guò)D求得A到C的距離，再經(jīng)過(guò)C求得A到B的距離。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 26,圖的最短路算法-Floyd,Q：怎么樣輸出最短路的方案??？ A：我們

15、可以另開(kāi)一個(gè)數(shù)組hisij，表示i到j(luò)點(diǎn)經(jīng)過(guò)了hisij點(diǎn)。初始化時(shí)hisij=i即可。 維護(hù)：i到j(luò)的距離可以被更新時(shí) hisij=k（枚舉的中轉(zhuǎn)節(jié)點(diǎn)）。 查詢(xún)：遞歸查找：i到j(luò)其中一個(gè)中轉(zhuǎn)節(jié)點(diǎn)是hisij，然后再找hisihisij和hishisijj直到這兩個(gè)值為i或者j即可。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 27,圖的最短路算法-Floyd,例題：香甜的黃油 P1828 題目簡(jiǎn)述：有n頭牛住在p個(gè)牧場(chǎng)里，牧場(chǎng)兩兩之間有一定距離?，F(xiàn)在FJ把所有奶牛集合在一個(gè)牧場(chǎng)里，請(qǐng)選擇一個(gè)合適的牧場(chǎng)，使得所有奶牛遷移的總距離最小。輸出最小值。 數(shù)據(jù)范圍：n=500,p=800,牧場(chǎng)間道路條數(shù)m

16、=1450（無(wú)向圖）,牧場(chǎng)間距離d=255。所有輸入數(shù)據(jù)為正整數(shù)。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 28,圖的最短路算法-Floyd,可以用Floyd沒(méi)差。 統(tǒng)計(jì)一下每個(gè)牧場(chǎng)到底有多少奶牛，F(xiàn)loyd之后枚舉每一個(gè)牧場(chǎng)作為最終牧場(chǎng)，計(jì)算遷移距離，最后取最小值即可。 復(fù)雜度Floyd p3 + 統(tǒng)計(jì)答案 p2 我洛谷AC不了，TLE70分，該怎么辦??？ 8003=5.12*108 5003=1.25*108 再過(guò)不了提交的時(shí)候開(kāi)O2優(yōu)化強(qiáng)行A掉吧，待會(huì)有好辦法AC這道題。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 29,圖的最短路算法-Floyd,例題：牛大賽 P2419 題目簡(jiǎn)述：給定n

17、頭牛和m條勝負(fù)關(guān)系，求排名已定的牛的個(gè)數(shù)（和其他所有牛勝負(fù)關(guān)系已定）。 數(shù)據(jù)范圍：n=100,m=4500。,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 30,圖的最短路算法-Floyd,Floyd 傳遞閉包。 勝利方向失敗方連邊，F(xiàn)loyd 改為tij|=tik 刪去i, lca或j, lca上最大的一條邊,洛谷網(wǎng)校冬令營(yíng) 2018.2,Page 63,拿M元買(mǎi)啤酒，N元可以買(mǎi)一瓶，4個(gè)瓶蓋換一瓶啤酒，2個(gè)空瓶換一瓶啤酒。可以向周?chē)藷o(wú)限制地借瓶蓋和瓶子，但前提是必須歸還同樣的物品。比如借了一個(gè)瓶子，最后就要還一個(gè)瓶子，不能用兩個(gè)瓶蓋代替一個(gè)瓶子去還。你的目標(biāo)是計(jì)算出最多能喝多少瓶酒。 N,M范圍在int范圍以?xún)?nèi)，保證M/N小于4e6。,休息題,洛谷網(wǎng)校冬令營(yíng)