集訓隊作業(yè)冬令營解題報告mst

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

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

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

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

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