圖論專題選講

1、圖論專題選講by acerlawsonA - A - 秋實(shí)大哥與連鎖快餐店秋實(shí)大哥與連鎖快餐店 題目大意：二維平面上有n個(gè)點(diǎn)，部分點(diǎn)是特殊點(diǎn)，添加長(zhǎng)度和最小的邊，使得任意一點(diǎn)都能至少能和一個(gè)特殊點(diǎn)連通。 首先，先解決一個(gè)子問(wèn)題：n個(gè)點(diǎn)的完全圖中，有m=n(n-1)/2條邊，求最小生成樹求最小生成樹。 對(duì)于完全圖: prim算法：時(shí)間復(fù)雜度O(n2)，空間復(fù)雜度O(n). Kruskal算法：時(shí)間復(fù)雜度O(mlogm) ，空間復(fù)雜度O(m). 在解決完全圖的最小生成樹中，prim更優(yōu)。A - A - 秋實(shí)大哥與連鎖快餐店秋實(shí)大哥與連鎖快餐店 題目大意：二維平面上有n個(gè)點(diǎn)，部分點(diǎn)是特殊點(diǎn)，添加長(zhǎng)度

2、和最小的邊，使得任意一點(diǎn)都能至少能和一個(gè)特殊點(diǎn)連通。接下來(lái)，再考慮第二個(gè)子問(wèn)題：二維平面上的n個(gè)點(diǎn)，添加長(zhǎng)度和長(zhǎng)度和最小的邊，使得整體聯(lián)通整體聯(lián)通。其實(shí)就是第一個(gè)子問(wèn)題的變形，n個(gè)點(diǎn)的完全圖，任意兩個(gè)點(diǎn)的邊權(quán)定義為這兩個(gè)點(diǎn)之間的歐幾里德距離，求最小生成樹。A - A - 秋實(shí)大哥與連鎖快餐店秋實(shí)大哥與連鎖快餐店 題目大意：二維平面上有n個(gè)點(diǎn)，部分點(diǎn)是特殊點(diǎn)，添加長(zhǎng)度和最小的邊，使得任意一點(diǎn)都能至少能和一個(gè)特殊點(diǎn)連通。 最后，我們回到原題，可以發(fā)現(xiàn)第二個(gè)問(wèn)題和原題的區(qū)別只是特只是特殊點(diǎn)的存在與否殊點(diǎn)的存在與否。那么如何解決特殊點(diǎn)呢？很簡(jiǎn)單啊！特殊點(diǎn)之間的邊權(quán)變?yōu)?就解決了！A - A - 秋實(shí)大

3、哥與連鎖快餐店秋實(shí)大哥與連鎖快餐店 題目大意：二維平面上有n個(gè)點(diǎn)，部分點(diǎn)是特殊點(diǎn)，添加長(zhǎng)度和最小的邊，使得任意一點(diǎn)都能至少能和一個(gè)特殊點(diǎn)連通。 如何實(shí)現(xiàn)？ 方法1.在更新邊權(quán)的時(shí)候： 如果兩個(gè)點(diǎn)都是特殊點(diǎn)，d(vi,vj)=0； 否則，d(vi,vj)=歐幾里德距離; 方法2.先把特殊點(diǎn)處理了，再把普通點(diǎn)處理了。B - B - 秋實(shí)大哥帶我飛秋實(shí)大哥帶我飛 題目大意：非負(fù)權(quán)無(wú)向圖中最短路方案數(shù)。 （無(wú)關(guān)緊要的題意補(bǔ)充：保證起點(diǎn)到終點(diǎn)一定可達(dá)。 題目來(lái)源：Topcoder srm div1 B 首先，最簡(jiǎn)單的，求起點(diǎn)到每個(gè)點(diǎn)i的最短路disti。 Dijkstra,spfa什么的隨便選一個(gè)亂搞一

4、下就行了。B - B - 秋實(shí)大哥帶我飛秋實(shí)大哥帶我飛 題目大意：非負(fù)權(quán)無(wú)向圖中最短路方案數(shù)。 接下來(lái)是重點(diǎn)，求方案數(shù)。首先我們總需要知道最短路可以經(jīng)過(guò)哪些點(diǎn)吧？我們可以倒著從終點(diǎn)往回走，通過(guò)一個(gè)普通的隊(duì)列來(lái)實(shí)現(xiàn)。先把終點(diǎn)t扔進(jìn)空隊(duì)列，每次那一個(gè)點(diǎn)i拿出來(lái)。對(duì)于點(diǎn)i的所有邊edge(i,j)，如果前驅(qū)distj=edge(i,j)+disti,那么就可認(rèn)為：一定能通過(guò)j點(diǎn)到達(dá)i的最短路disti，同時(shí)把j點(diǎn)也加進(jìn)隊(duì)列 。直到隊(duì)列為空為止。B - B - 秋實(shí)大哥帶我飛秋實(shí)大哥帶我飛 題目大意：非負(fù)權(quán)無(wú)向圖中最短路方案數(shù)。B - B - 秋實(shí)大哥帶我飛秋實(shí)大哥帶我飛 題目大意：非負(fù)權(quán)無(wú)向圖中最短

5、路方案數(shù)。 這樣就能知道所有最短路徑中經(jīng)過(guò)的所有可能點(diǎn)有哪些了。然而看上去對(duì)求方案數(shù)并沒(méi)有什么卵用。 其實(shí)只要在過(guò)程中稍稍修改，就可以求出答案了。B - B - 秋實(shí)大哥帶我飛秋實(shí)大哥帶我飛 題目大意：非負(fù)權(quán)無(wú)向圖中最短路方案數(shù)。 對(duì)于每個(gè)點(diǎn)i，定義兩個(gè)值ansi和waysi。 ansi表示從這個(gè)點(diǎn)i到終點(diǎn)最短路的總方案數(shù)。 waysi,表示從這點(diǎn)i到終點(diǎn)最短路中還有waysi的方案數(shù)的方案數(shù)沒(méi)有分配給前驅(qū)j點(diǎn)（滿足distj=edge(i,j)+disti的點(diǎn)）B - B - 秋實(shí)大哥帶我飛秋實(shí)大哥帶我飛 題目大意：非負(fù)權(quán)無(wú)向圖中最短路方案數(shù)。 具體實(shí)現(xiàn)過(guò)程： 每次從隊(duì)列中拿隊(duì)首元素u出來(lái)：

6、 遍歷所有與它相鄰的邊e如果diste.v=distu+e.d，那么分配給v:wayse.v+=waysu 遍歷完邊以后，把waysu分配給自己:ansu+=waysu。 這樣waysu就被分配完了，置0。B - B - 秋實(shí)大哥帶我飛秋實(shí)大哥帶我飛 題目大意：非負(fù)權(quán)無(wú)向圖中最短路方案數(shù)。waysanswaysanswaysanswaysansB - B - 秋實(shí)大哥帶我飛秋實(shí)大哥帶我飛 題目大意：非負(fù)權(quán)無(wú)向圖中最短路方案數(shù)。 接下來(lái)是細(xì)節(jié)問(wèn)題： 重邊：沒(méi)影響?。?0邊：從終點(diǎn)往回走的過(guò)程中只要遇到0邊答案就是無(wú)數(shù)條?。?算法：Spfa的思想求方案數(shù)！也可以用其他方法亂搞：拓?fù)渑判颉fs之類

7、等等。C - C - 秋實(shí)大哥與時(shí)空漫游秋實(shí)大哥與時(shí)空漫游給定初始的時(shí)間St和地點(diǎn)Sp，現(xiàn)在要求求出一組合法路徑使得，能夠在Tt時(shí)間之前到達(dá)Pt。每一條邊（傳送門）定義：起點(diǎn)a,終點(diǎn)b,起始時(shí)間c,終點(diǎn)時(shí)間d。如果想走這條邊，那么就必須在c時(shí)刻之前到達(dá)a，等候到c時(shí)刻的時(shí)候通過(guò)該邊到達(dá)b點(diǎn)的d時(shí)間。題意很復(fù)雜？沒(méi)有頭緒？其實(shí)很簡(jiǎn)單！其實(shí)很簡(jiǎn)單！C - C - 秋實(shí)大哥與時(shí)空漫游秋實(shí)大哥與時(shí)空漫游首先，每條邊走一次就夠了。走兩次反而會(huì)致使一個(gè)星球上同時(shí)存在兩個(gè)秋實(shí)大哥。接下來(lái)，我們定義對(duì)每個(gè)點(diǎn)定義數(shù)組timi表示目前為止最早能到表示目前為止最早能到i點(diǎn)的時(shí)刻點(diǎn)的時(shí)刻。顯而易見，對(duì)于起點(diǎn)，timS

8、p=St，對(duì)于其他點(diǎn)，timi=infC - C - 秋實(shí)大哥與時(shí)空漫游秋實(shí)大哥與時(shí)空漫游然后，對(duì)于每個(gè)點(diǎn)i，我們對(duì)所有邊起點(diǎn)邊起點(diǎn)為i的按出發(fā)時(shí)間出發(fā)時(shí)間c從大到小排序。這部預(yù)處理的時(shí)間復(fù)雜度最多是mlogm。這樣排序是有目的性的：對(duì)于點(diǎn)i的每個(gè)出邊e，如果這個(gè)邊e能走，那么排在它前面的邊都可以走。C - C - 秋實(shí)大哥與時(shí)空漫游秋實(shí)大哥與時(shí)空漫游最后，我們O(m)的時(shí)間復(fù)雜度求出答案。這也就是為什么邊數(shù)敢放5*105的原因。對(duì)于每個(gè)點(diǎn)i在定義一個(gè)zzi=0，表示現(xiàn)在已經(jīng)訪問(wèn)完了zzi-1號(hào)邊，準(zhǔn)備訪問(wèn)zzi邊節(jié)點(diǎn)。定義個(gè)一個(gè)隊(duì)列Q，開始時(shí)把起點(diǎn)加入隊(duì)列。每次取隊(duì)首元素x出來(lái)，從第zzx條邊e開始向其他點(diǎn)的time.b更新，（time.d?）如果更新成功，將e.b入隊(duì)。直到遇到某條邊的c要小于timx。直到隊(duì)列為空為止，做完了。C - C - 秋實(shí)大哥與時(shí)空漫游秋實(shí)大哥與時(shí)空漫游C - C - 秋實(shí)大哥與時(shí)空漫游秋實(shí)大哥與時(shí)空漫游最后只需要判斷最后只需要判斷timTp=Tt