集訓(xùn)隊(duì)作業(yè)冬令營(yíng)解題報(bào)告mst

1、最小生成樹【題目簡(jiǎn)述】給定個(gè)點(diǎn)，條邊的無(wú)向帶權(quán)連通圖，需要通過(guò)改變邊的權(quán)值使得該圖的最小生成樹唯一，把一條邊的權(quán)值減 1 的花費(fèi)是,權(quán)值加1的花費(fèi)是,求最小花費(fèi)。【數(shù)據(jù)范圍】對(duì)于50%的數(shù)據(jù), 500000, 1000000, min(, ) = 1, max(, ) = 109對(duì)于后50%的數(shù)據(jù)，給定數(shù)據(jù)?！绢}目類型】半“傳統(tǒng)題”【試題點(diǎn)】割點(diǎn)+局部搜索【題目分析】由于是要求最小生成樹唯一，那么顯然，對(duì)于每一條邊，權(quán)值的改變量不會(huì)超過(guò) 1。算法 1：對(duì)于前兩個(gè)點(diǎn)， = 109, = 1，所以只能進(jìn)行給邊權(quán)加1的操作。由得，對(duì)于權(quán)值相同的邊的集合，所的。因此，在的同時(shí)，把權(quán)值相同的邊放在一個(gè)階

2、段做，把權(quán)值比的連通性狀況是一樣它小的邊的圖連通性縮點(diǎn)，然后用當(dāng)前權(quán)值的邊圖，在這中找出所有割邊，那么這些割邊是一定在最小生成樹中的，那么這些邊的權(quán)值不用改變，對(duì)于一個(gè)個(gè)點(diǎn)條邊的強(qiáng)塊，需要把權(quán)值改大的邊有 ( 1)條，所以就是 ( 1)?？臻g復(fù)雜度：()時(shí)間復(fù)雜度：( log )期望得分：20分算法 2：對(duì)于3,4,5三個(gè)點(diǎn)， = 1, = 109,所以只能進(jìn)行給邊權(quán)減1的操作。 _那么像算法一一樣，對(duì)相同權(quán)值的邊構(gòu)圖，去掉割邊，然后 對(duì)于一個(gè)個(gè)點(diǎn)條邊的強(qiáng) 1。塊，需要把權(quán)值改小的邊有 1條，所以就是結(jié)合算法一，就可以解決前5個(gè)點(diǎn)?？臻g復(fù)雜度：()時(shí)間復(fù)雜度：( log )期望得分：50分算法

3、 3：如果題目是給定一棵樹,讓它成為唯一的,那么題目會(huì)變得簡(jiǎn)單一點(diǎn)。那么能不能進(jìn)行猜想：對(duì)于原圖中的任意一棵,把它變成唯一的所需要的代價(jià)都是一樣的且是最小的。假設(shè)這個(gè)猜想是正確的。那么對(duì)于前20%的點(diǎn)，發(fā)現(xiàn)都是加操作，那么只要先求出任意一棵,于是肯定是對(duì)一些非邊進(jìn)行+1操作。所以只要枚舉所有非上的邊，求出它所連接的兩個(gè)點(diǎn)在樹上路徑上的最大值，如果等于這條邊的權(quán)值，那么就需要進(jìn)行加操作。而詢問(wèn)樹上路徑權(quán)值最大值個(gè)點(diǎn)的,然后用倍增算法分別求出兩條路徑上的最大值?？梢韵惹蟪鰞蓪?duì)于3,4,5三個(gè)點(diǎn)，都是減的操作，同樣，也只要先求出任意一棵,于是肯定是對(duì)一些邊進(jìn)行1操作。而進(jìn)行減操作的邊一定是由于某個(gè)環(huán)

4、中有一條非邊與它權(quán)值一樣。所以可以先對(duì)所有非邊按權(quán)值從小到大排序，然后依次枚舉非邊，把兩個(gè)點(diǎn)之間的路徑應(yīng)的修改，然后用并查集并起來(lái)就行了。對(duì)于后50%的點(diǎn)，這兩種方法并不能有效的解決。一邊，進(jìn)行相空間復(fù)雜度：()時(shí)間復(fù)雜度：( log )期望得分：50分算法 4：在算法 3 中，假設(shè)了一個(gè)結(jié)論是正確的，然后對(duì)應(yīng)的獲得了兩種算法。但是對(duì)于后50%的數(shù)據(jù)，加減同時(shí)存在，于是需要其他算法。再次假設(shè)那個(gè)結(jié)論是正確的。那么先任意求出一棵,考慮每一條非邊(, ),那么在上到的路徑上與邊(, )權(quán)值相同的邊是需要考慮的邊，這兩者之間可以建立關(guān)系：要不把邊(, )權(quán)值加1，花費(fèi)為，要么就把所有在那條路徑上的與

5、它權(quán) 值相同的邊權(quán)值都減1,每條花費(fèi)為,要使總花費(fèi)最小。那么這個(gè)就是一個(gè)明 顯的最小割模型，求出最大流即可。到這里，貌似問(wèn)題解決了。其實(shí)不然！這些算法都是基于算法3中那個(gè)假設(shè)的：對(duì)于原圖中的任意一棵,我 們把它變成唯一的所需要的代價(jià)都是一樣的且是最小的。然而對(duì)于這個(gè)假設(shè)，只能證明其在只有一種操作的時(shí)候是正確的， _而當(dāng)加減操作同時(shí)存在的時(shí)候是有反例證明這個(gè)假設(shè)是錯(cuò)誤的！反例如下：10000 個(gè)點(diǎn)的鏈100個(gè)點(diǎn)的鏈100個(gè)點(diǎn)的鏈兩兩之間有邊10000 條每條邊的權(quán)值都是1，加減的花費(fèi)也都是1，那么如果一開始選擇了棕色的樹，按以上算法求出的 要修改10000條邊，然而，如果選擇的是一條棕色的邊和下面的一條邊，那么 只要修改199條邊。所以這個(gè)猜想是不成立的，但是這個(gè)算法還是能拿到比較高的分?jǐn)?shù)，我在考場(chǎng)上就是用了這個(gè)算法跑了后5個(gè)點(diǎn)，然后用了算法3跑前5個(gè)點(diǎn)，然后得到了80分?？臻g復(fù)雜度：(2) -事實(shí)上遠(yuǎn)遠(yuǎn)不到時(shí)間復(fù)雜度：(, 2)-事實(shí)上遠(yuǎn)遠(yuǎn)不到期望得分：7080分算法 5：對(duì)于后5個(gè)點(diǎn)，沒有很好的解決辦法，因此只能使用搜索的方法。對(duì)于割邊，一定不用進(jìn)行修改，那么只要對(duì)于每個(gè)強(qiáng)塊進(jìn)行分別搜索即可。而通過(guò)分析發(fā)現(xiàn)，后5個(gè)點(diǎn)每個(gè)強(qiáng)快的。塊的點(diǎn)數(shù)都很少，所以還是比較空間復(fù)雜度：() 時(shí)間復(fù)雜度：