資源描述：
《國(guó)家集訓(xùn)隊(duì)2005論文集 何林》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、數(shù)據(jù)關(guān)系的簡(jiǎn)化長(zhǎng)沙雅禮中學(xué)何林常用的數(shù)據(jù)關(guān)系：線性序列，樹，圖1243651(1,1)2(2,1)4(3,1)3(4,4)5(5,4)6(6,4)12345781242585272131坐船問題雅禮中學(xué)有n個(gè)學(xué)生去公園劃船。一條船最多可以坐兩個(gè)人。如果某兩個(gè)學(xué)生同姓或者同名就可以坐在一條船上。學(xué)校希望每個(gè)同學(xué)都坐上船，同時(shí)學(xué)校想要租用最少的船。請(qǐng)問：學(xué)校至少要租多少船？伍昱伍平何林何剛黃剛何凡伍昱伍平黃剛何剛何林何凡伍昱伍平黃剛何剛何林何凡最優(yōu)解OR圖-->樹伍昱伍平黃剛何剛何林何凡一個(gè)包含n個(gè)點(diǎn)的無向圖同名或者同姓的人之間連一條邊圖模型最小邊
2、覆蓋任意圖最大匹配！伍昱伍平何林何剛黃剛何凡伍昱伍平黃剛何剛何林何凡樹結(jié)構(gòu)一片森林每個(gè)節(jié)點(diǎn)和左孩子同姓每個(gè)節(jié)點(diǎn)和右孩子同名樹的構(gòu)造首先假設(shè)所有人是一個(gè)連通圖黃剛雷鋒雷濤黃濤歐陽鋒黃嘎張嘎雷震子黃藥師周濤張藥師樹的構(gòu)造首先假設(shè)所有人是一個(gè)連通圖雷鋒雷濤黃濤歐陽鋒黃嘎張嘎雷震子黃藥師周濤黃剛張藥師沒有左兒子了樹的構(gòu)造首先假設(shè)所有人是一個(gè)連通圖雷鋒雷濤黃濤歐陽鋒黃嘎張嘎雷震子黃藥師周濤黃剛張藥師樹的構(gòu)造首先假設(shè)所有人是一個(gè)連通圖黃剛雷鋒雷濤黃濤歐陽鋒黃嘎張嘎雷震子黃藥師周濤張藥師歐陽濤樹的構(gòu)造首先假設(shè)所有人是一個(gè)連通圖黃剛雷鋒雷濤黃濤歐陽鋒黃嘎張嘎雷
3、震子黃藥師周濤張藥師歐陽濤沒有右兒子樹的構(gòu)造首先假設(shè)所有人是一個(gè)連通圖黃剛雷鋒雷濤黃濤歐陽鋒黃嘎張嘎雷震子黃藥師周濤張藥師歐陽濤樹的匹配黃剛雷鋒雷濤黃濤歐陽鋒黃嘎張嘎雷震子黃藥師周濤張藥師歐陽濤分析葉子節(jié)點(diǎn)獨(dú)子！樹的匹配黃剛雷鋒雷濤黃濤歐陽鋒黃嘎張嘎雷震子黃藥師周濤張藥師歐陽濤獨(dú)子的情況他們坐一條船剩下的樹依然是連通的樹的匹配黃剛雷鋒雷濤黃濤歐陽鋒黃嘎張嘎雷震子黃藥師張藥師分析葉子節(jié)點(diǎn)落單！樹不連通！不是獨(dú)子樹的匹配黃剛雷鋒雷濤黃濤歐陽鋒黃嘎張嘎雷震子黃藥師張藥師分析葉子節(jié)點(diǎn)樹的匹配非獨(dú)子的情況每次讓兩個(gè)人坐上一條船樹始終保持連通假設(shè)樹中有n個(gè)
4、點(diǎn)，[(n+1)/2]條船即可容納所有人。這無疑是最優(yōu)解。樹的匹配設(shè)森林中有m棵樹，所有樹的規(guī)模是n1,n2,…,nm。對(duì)每棵樹分別處理。答案是∑(i=1..m)[(ni+1)/2]森林的匹配圖-->樹小結(jié)伍昱伍平黃剛何剛何林何凡任意圖最大匹配！伍昱伍平黃剛何剛何林何凡簡(jiǎn)單貪心O(n2)或O(n3)的時(shí)間復(fù)雜度編程復(fù)雜度很高O(n)的時(shí)間復(fù)雜度編程復(fù)雜度很低樹的統(tǒng)計(jì)一棵樹含有n個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)編號(hào)為1,2,3,…,n。定義t(v)為v的后代中所有編號(hào)小于v的節(jié)點(diǎn)個(gè)數(shù)。求t(1),t(2),t(3),…,t(n)。樹-->線性樹-->線性710193
5、411685151221413t(9)=3t(10)=1t123456789101112131415000001603100020對(duì)每個(gè)點(diǎn)，逐個(gè)檢查其后代。時(shí)間復(fù)雜度O(n2)。當(dāng)n>=30000就不可承受。樹-->線性后代如何把這個(gè)“先后”順序表現(xiàn)出來呢樹-->線性710193411685151221413線性一個(gè)序列中元素之間的先后關(guān)系十分明顯710142131911658315124樹-->線性710193411685151221413線性一個(gè)序列中元素之間的先后關(guān)系十分明顯710142131911658315124對(duì)應(yīng)后代多出來的部分9
6、樹-->線性710193411685151221413線性逆序DFS遍歷710142131911658315124樹-->線性710193411685151221413線性對(duì)應(yīng)后代多出來的部分9710142131911658315124樹-->線性710193411685151221413710142131911658315124743121596851111014132DFS遍歷逆DFS遍歷樹-->線性710193411685151221413710142131911658315124743121596851111014132DFS遍歷逆DF
7、S遍歷后代！重疊-->容斥原理樹-->線性710193411685151221413710142131911658315124743121596851111014132DFS遍歷逆DFS遍歷9的直系祖先紅+藍(lán)+黃=全部+后代樹-->線性710193411685151221413710142131911658315124743121596851111014132DFS遍歷逆DFS遍歷紅+藍(lán)+黃=全部+后代紅：DFS序列中節(jié)點(diǎn)v后比他小的數(shù)的個(gè)數(shù)藍(lán)：逆DFS序列中節(jié)點(diǎn)v后比他小的數(shù)的個(gè)數(shù)黃：v的直系祖先中比v小的節(jié)點(diǎn)個(gè)數(shù)全部：v-1樹-->線性紅+
8、藍(lán)+黃=全部+后代紅：DFS序列中節(jié)點(diǎn)v后比他小的數(shù)的個(gè)數(shù)藍(lán)：逆DFS序列中節(jié)點(diǎn)v后比他小的數(shù)的個(gè)數(shù)黃：v的直系祖先中比v小的節(jié)點(diǎn)個(gè)數(shù)全部：v-1紅：
