拓撲排序圖算法sat_歐拉h(huán)amilton路教學課件(存儲版)
【正文】 . *** 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 126 例題分析 ?容易聯(lián)想到歐拉路 –每個單詞相當于在首字母和尾字母之間連一條邊 –得到一個最多 26個點的有向圖，求歐拉路即可 –注意先判斷 連通性 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 127 例題分析 ? Ural1124 Mosaic –有 M種卡片，每種有 N張，初始時放在 M個盒子里，每個盒子里有 N張，但是可能有某些卡片放錯了位置，因此需要進行一些移動，最后使得每張卡片都放到它應該在的盒子（第 1種卡片都放入盒 1，第 2種卡片都放入盒 2 …）。 ?權值為兩點間最短路 ?如果是有向圖，二分圖帶權匹配 ?如果是無向圖，一般圖帶權匹配 …… 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 135 Hamilton路 ?定義：經(jīng)過圖中每個 點 恰好一次的路 ?經(jīng)典 NP完全問題，尚未發(fā)現(xiàn)多項式算法 ?常見解決方案 –狀態(tài)壓縮 DP (點數(shù)較少的情況 , 如 N=15) –利用問題特殊性 (對某些特殊的圖有多項式算法 ) 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 136 Hamilton路的 DP解法 ?對于點數(shù)較少的情況，可以用狀態(tài)壓縮的DP來做。 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 140 競賽圖的 Hamilton路 –構造方法： ?假設我們已經(jīng)找到了一條路 V1→ V2→ …→ Vn ?我們可以把每個新點 p都加進這條路里面去，從而最終得到一條 Hamilton路。 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 138 例題分析 ? Sample Input 3 0 1 1 1 0 1 0 0 0 ? Sample Output 1 3 2 1 3 1 3 2 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 139 例題分析 ?競賽圖：特殊的有向圖，對于任意點對(i,j)都有邊 (i,j)或邊 (j,i) ?實際上，競賽圖的 Hamilton路一定存在，并且可以在多項式時間內構造出來。 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 130 例題分析 ? Ouroboros Snake –TOJ1070 (此處略有改動 ) –題目大意：給定長度 k，進制 b，求出一個由[0..b1]的數(shù)組成的環(huán)狀序列，使得從環(huán)上任一個位置開始的 k位數(shù)表示一個唯一的 b進制數(shù)。 t = t + 1。 –對重邊、自環(huán)的情況仍適用。 –(4) 轉步驟 (2), 直到所有點都輸出完畢 –如果在執(zhí)行過程中發(fā)現(xiàn)找不到入度為 0的點 , 說明圖中存在環(huán) 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 1 15 拓撲排序 2 1 3 4 8 7 5 6 拓撲序： 1 3 2 4 5 6 7 8 (不唯一 ) 如何求出字典序最小的拓撲序列 ? 425130 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0
環(huán)評公示相關推薦
鄂ICP備17016276號-1