國(guó)家集訓(xùn)隊(duì)作業(yè)sgu413解題報(bào)告

1、SGU413 Berland Divi解題問題簡(jiǎn)述：給出一個(gè)頂點(diǎn)數(shù)為偶數(shù)的連通圖，將其分成若干不相交的子圖，使得每個(gè)子圖都是一棵頂點(diǎn)數(shù)大于 1 的樹。(題目沒對(duì)無(wú)解時(shí)如何輸出做出解釋)問題分析：本題要將一個(gè)圖分解，那么如何分解?如何保證一個(gè)子圖是一棵樹呢？這都是非常麻煩的事情。另外圖的頂點(diǎn)是偶數(shù)，這個(gè)條件有什么用呢？如果頂點(diǎn)數(shù)為奇數(shù)，顯然一個(gè)長(zhǎng)度為 3 的環(huán)就是無(wú)解的，那么偶數(shù)是否就意味著一定有解呢？讓一步步分析。直接把圖分解是比較的，可以嘗試?yán)脠D的生成樹的某些性質(zhì)，找出圖上已有的樹。比較容易想到的當(dāng)然就是簡(jiǎn)單的 DFS 生成樹了。那么DFS 生成樹有什么性質(zhì)呢?不難發(fā)現(xiàn)生成樹上的任意節(jié)點(diǎn)和

2、其兒子組成的子圖在原圖中肯定是一棵樹。因?yàn)閮鹤又g是不會(huì)有邊相連的，否則由 DFS 的性質(zhì)，他們不可能成為兄弟。這樣不難得出一個(gè)貪心的算法，利用把任意節(jié)點(diǎn)和其兒子的子圖在原圖中都是一棵樹的性質(zhì)，可以從 DFS 樹的葉子開始往上分組，把當(dāng)前節(jié)點(diǎn)和未分組的兒子分為同一組。如果不存在未分組的兒子則當(dāng)前節(jié)點(diǎn)標(biāo)記為未分組。下圖是一個(gè)例子：相同顏色的分為一組顯然這個(gè)算法存在一個(gè)缺陷，就是根節(jié)點(diǎn)可能沒有分進(jìn)任何一組。如下圖左邊所示：這該如何解決呢？實(shí)際上該算法成功與否與DFS 生成樹的形態(tài)有很大關(guān)系。對(duì)于上圖的情況，如果把原來(lái)根紅色的兒子作為新根就能得到右圖的可行可以采用枚舉根甚至隨機(jī)改變 DFS 順序的方

3、法來(lái)多次求解。而對(duì)解。因此于SGU 的數(shù)據(jù)，只需要枚舉根就可以Accept 了。這個(gè)算法十分簡(jiǎn)潔，而且正確率極高，時(shí)間復(fù)雜度為 O(NM)。但這樣的算法并不完美，而且沒有利用到 N 為偶數(shù)的性質(zhì)，分析。還需進(jìn)一步算法改進(jìn)：上文算法只在根節(jié)點(diǎn)處會(huì)出現(xiàn)問題，就從這下手。首先還是按照上文的算法遍歷圖，如果根節(jié)點(diǎn)已經(jīng)在某組內(nèi)則已得到可行解，否則先嘗試把根添加到某一組內(nèi)，如果根只與該組中的一個(gè)點(diǎn)相連則直接添加，同樣得到一組可行解。而如果無(wú)法添加，為得到可行解勢(shì)必要改變?cè)械姆纸M方式。并且要注意到此時(shí)任一組與根之間至少有兩條邊。讓先來(lái)根節(jié)點(diǎn)兒子所在的組。如果該組只有兩個(gè)點(diǎn)，則此時(shí)根必然與這兩個(gè)點(diǎn)形成一個(gè)長(zhǎng)

4、度為 3 的環(huán)，無(wú)法通過調(diào)整得到可行解。而如果該組不止兩個(gè)節(jié)點(diǎn)，由于每一組都是一個(gè)父親帶上若干個(gè)兒子的形式，必然存在某個(gè)兒子與根有邊相連，這樣把它和根分成一組，其他分組方式不變就可行解。下圖是一個(gè)例子：實(shí)線為 DFS 樹邊，虛線為原圖的非樹邊。那么當(dāng)所有根的兒子所在的組都只有兩個(gè)點(diǎn)時(shí)，又該怎么辦呢?這時(shí)就要利用 N 為偶數(shù)的條件了。顯然根以及根的兒子所在的組的所有節(jié)點(diǎn)的總數(shù)為奇數(shù)，那么剩下的節(jié)點(diǎn)個(gè)數(shù)也為奇數(shù)。即下圖所有綠色三角形(每個(gè)三角形為一棵去掉根的)中的點(diǎn)的個(gè)數(shù)為奇數(shù)。由奇偶分析知，必然有一個(gè)的三角形節(jié)點(diǎn)數(shù)為的奇數(shù)(下圖中用深綠色表示)，加上其的根便總共有偶數(shù)個(gè)節(jié)點(diǎn)，而且這棵是連通的。這樣不就和原問題的條件相同了嗎?因此可以把這部分遞歸求解，而把多余的那個(gè)節(jié)點(diǎn)和根分為同一組，其他不變即可。按照上文的算法，每次要么小的子問題，所以到最后已經(jīng)得到可行解，要么得到一個(gè)規(guī)模減會(huì)得出正確解。而且遞歸最多進(jìn)行 N/2 次