自選題解解題報告

1、tack解江蘇tack解江蘇省常州高級中 1題一座國家有 N 個城市以及 M 條連接兩個城市的雙向道路?，F(xiàn)在這個國家被籠罩道路。作分子頭目的你想知道，對題一座國家有 N 個城市以及 M 條連接兩個城市的雙向道路。現(xiàn)在這個國家被籠罩道路。作分子頭目的你想知道，對于 Q 條道路，如的陰影下，然分子只把它摧毀后想要使得所有城市連通，所有道路的長度之和的最小值是多少（如果無法連通所有城市，輸出”Not Connected。（滿足 N 10000， M 100000， Q 100000，原圖可能有出現(xiàn)兩座城市之間有多條路，可能出現(xiàn)一個城市有連接自己的道路時間限制：1s，空間限制32MB讀完題可以很快得到

2、一個簡單的模型：有一個 N 個節(jié)點 M 條邊的無向圖（可能有自環(huán)、重最容易想到的是樸素的模擬算法。每次把一條邊去掉，做原圖的最小生成樹，然后輸出答案或者判斷圖不連通。然而無論使用堆優(yōu)化的 prim 算法還是 kruskal 算法，由于詢問 Q 達到了100000O(QNlogM)和O(QMlogM)，想要C此題無疑是不實際的。無法使用自己所得心應手的算法來解決此題的原因是什么呢？因要操作的模型圖，而圖的優(yōu)美性質并不多，導致開始無法順利解決此題。而樹卻擁有許多優(yōu)美的性質而最小生成樹更是有無數(shù)有趣的結論和特點。簡潔優(yōu)美的最小生成樹來考慮。不妨換一個算法實一個很直接的想法是把原圖的最小生成樹求出來，

3、再把刪除邊化為對樹的操作。一步，利用最小生成樹的特點來解決這個問題。一把原來的最小生成樹求出來以后，顯然只有刪掉樹上的邊才會改變。而刪掉一條樹后，由 Kruskal 算法的性容易知道樹上的其他邊在最終解中保持不變。因此刪邊后樹分成了兩個點集的目標就是在這兩個點集間找一條權值最小的新的最小生成樹算法 1：求出最小生成樹，對于每一個刪除邊的詢問，利用并查集將點集分為兩部分，再舉邊；對于所兩個不同點集的邊，尋找一條最小的時間復雜度： O(MlogM Q (N M空間復雜度： O(N M這樣簡單的該進后就將原來枚舉的復雜度的 log 因子去掉了。雖然這個算法的時間雜度仍然不令人滿意，不已經(jīng)看到了成功的

4、曙光了繼續(xù)思剛才的算法時間復雜度不能令人滿意的原因。對于一次刪除操作后，原樹的態(tài)只有很小的改卻將原樹完全重新構造了出來；而且在枚舉邊的過程中，也出現(xiàn)很多冗余。能夠如何改進呢2把原圖中除最小生成樹以外的邊叫做“待用邊”，上嘗試每次刪掉樹邊，在待邊中尋找一條連接兩點集且最小的邊，但這一步難以把原圖中除最小生成樹以外的邊叫做“待用邊”，上嘗試每次刪掉樹邊，在待邊中尋找一條連接兩點集且最小的邊，但這一步難以實現(xiàn)能否反過來想：找出每條待邊能對哪些樹邊產生影響。有了這樣的思路都會形成一個環(huán)，正是環(huán)上的樹邊會被這條待用邊影響由于每個環(huán)與原 MST 的交都是樹上的一條路得出了如下算法：構建了 后，對于圖的其他

5、邊 (X,Y)，用 Length(X,Y) 更新樹上的路徑 (X,Y) 中的所有樹邊；每條樹。到了這一步，問題又化歸為樹上的路徑問題，利用邊的 DFS 序列或算法 2：求出最小生成樹，對于每一條連接 u,v 的非樹邊，更新 u 到 v 的路徑上所有樹邊，樹鏈剖分時間復雜度： O(MlogM Mlog2N 空間復雜度： O(N M動態(tài)樹時間復雜度： O(MlogM MlogN 空間復雜度： O(N M看起來這題已經(jīng)能夠十分出色的解決了，然后似還能夠改進和優(yōu)化，我仍然不能滿于當前的算法。樹鏈剖分的復雜度有 log2N 的因子，稍不注意常數(shù)就會導致超時；而動態(tài)樹又是比較難實現(xiàn)的東西，容易寫錯且常數(shù)也

6、很大。實驗證明，以上兩種算法即使經(jīng)過很好的優(yōu)化在評測時仍然是超時。由于這題第一步解決更新樹邊的時候是須借助高級數(shù)據(jù)結構來高效。如對于非樹邊進行排序呢驚訝地發(fā)現(xiàn)完全不需要多么高深的數(shù)據(jù)結構了，僅僅是一個一維數(shù)組就可以解決這個問題定義 Length Length(u,v)i 為邊 (u,v)i 的長只需按照 Length(u,v)i 從小到大枚舉邊行更新，并且保證每條邊只被更新一次即可。對于一條非樹邊 u,v，求出 LCA(u,v)，然后更新這一點很容易，可以使用類似并查集路徑壓縮的方法實現(xiàn)，只未被更新的邊即可 (因為有路徑壓縮，不一定要實)。在每次更新時不斷的指針上走，直到走到LCA(u,v)

7、為止算法 3：求出最小生成樹，對于每一條連接 u,v 的非樹邊排序，從小到大枚舉非樹邊，利用類此于并查集的方法更新 u 到 v 的路徑上所有樹邊。時間復雜度： O(MlogM MlogN 空間復雜度： O(NlogN M至此，問解決4小解決此問題的關鍵是把復雜的圖模型改變?yōu)樽钚∩蓸涞哪Ｐ停缓罄脭?shù)據(jù)結構體用的離線方法大大降低了時間和編程復雜度，得到了一個簡潔高效的算法35代#include #include #include #include using namespaFILE *fin=fopen( 1703.in , r ); struct edge5代#include #include #include #include using namespaFILE *fin=fopen( 1703.in , r ); struct edgea,edge b)return m)return void if(a=b) return a; return void 4iu=u) if(deepfau