拓撲排序圖算法sat_歐拉h(huán)amilton路教學(xué)課件(已改無錯字)
2022-10-13 09:37:07 本頁面
【正文】 0 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)想到歐拉路 –每個單詞相當(dāng)于在首字母和尾字母之間連一條邊 –得到一個最多 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張，但是可能有某些卡片放錯了位置，因此需要進行一些移動，最后使得每張卡片都放到它應(yīng)該在的盒子（第 1種卡片都放入盒 1，第 2種卡片都放入盒 2 …）。 –一次移動是指把一張卡片從當(dāng)前手邊的盒子里拿出放到另一個盒子，或者不拿卡片，只是把手從當(dāng)前的盒子處移到另一個盒子處。 –求最少的移動次數(shù) (M=500, n=50) 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 128 例題分析 ? Sample Input 4 3 1 3 1 2 3 3 1 2 2 4 4 4 ? Sample Output 6 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 129 例題分析 –如果盒子 i里面有一張卡片 j，就把 i,j之間連一條邊，表示至少要有一次從 i到 j的移動。容易發(fā)現(xiàn)這樣建圖后每個點的出度必然等于入度（因為初始時盒子里就有 N張卡片，后面拿出多少張也就要拿入多少張），也就是說對于每個連通分量，歐拉回路必定存在，最少的移動次數(shù)實際上就是邊的總數(shù)。 –在不同的連通分量之間必然要有一次空著手的移動。因此最后的答案就是 邊數(shù) +連通分量數(shù) 1（第一次開始時手可以在任何位置）。 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ù)。 (1=b=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 131 例題分析 ?當(dāng) k=3, b=2時，一個合法的環(huán)為 : 0 0 0 1 0 1 1 1 ?數(shù)學(xué)問題 ?? 沒有好的辦法 ?暴力搜索 ?? 復(fù)雜度為 O(b^(b^k))，無法接受 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 132 例題分析 ?對于一個 k1位 b進制數(shù) i，如果我們把 i的最高位去掉，在最低位補上一位后，能得到數(shù) j，就連一條邊 (i,j) ?我們得到一個節(jié)點數(shù)為 bk1的有向圖，每個節(jié)點的入度和出度都為 b ?這個圖存在歐拉回路，從歐拉回路即可構(gòu)造出原序列！ ?復(fù)雜度僅為 O(E)即 O(b*(b^k)) 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 133 中國郵路問題 ?邊上有權(quán)值，從任意一點開始，經(jīng)過每條邊至少一次并回到起點，求最短的距離 ?若存在歐拉回路，所有邊之和即為結(jié)果 ?若不存在 …… 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 134 中國郵路問題 ?奇數(shù)度的
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1