Re: [ACM ] 11597-Spanning Subtree

看板C_and_CPP作者bleed1979時間15年前 (2010/04/05 17:10)推噓9(9推 0噓 20→)

留言29則, 5人參與討論串2/8 (看更多)

借圖用一下１　２　　　１　２　　　１　２ ●─●　　　●─●　　　●　● │╳│　＝　　／　　∪　│＼│ ●─●　　　●─●　　　●　● ３　４　　　３　４　　　３　４產生的數列 1 - 2 - 3 - 4 端點中間點中間點端點 2 - 4 - 1 - 3 端點中間點中間點端點你會發現端點對是(1,4)(2,3) 6個點只看端點。端點對會是(1,6)(2,5)(3,4) 400個點只看端點。端點對會是(1,400)(2,399)(3,398).....(200,201) 如果你還有多餘的時間寫個dfs跑出所有生成樹。可能會找出 1 - 6 - 5 - 4 - 3 - 2 3 - 6 - 4 - 2 - 5 - 1 這兩棵生成樹，然後跑來講說端點對(1,2)(3,1)不符合我所講的。可是，兩組解並非"最大數量"，可以產生很多種類似的這種兩組解。但是依循這兩組解再去產生第三組解，你會發現生不出來。為什麼生出來？細看點5和點6 點5只剩下3可以連接，點6只剩下2可以連接。所以雛型是 5 - 3 - ... - ... - 2 - 6 ...的地方讓你填1和4，可是怎麼填都只會和樹1或樹2重複到。 5 - 3 - 1 - 4 - 2 - 6 其中的4 - 2和樹2是一樣的。不合。 5 - 3 - 4 - 1 - 2 - 6 其中的3 - 4和樹1是一樣的。不合。所謂的n / 2解答在於 6個點的點1，他的連接選擇為 2, 3, 4, 5, 6, 總共5種選擇。但他會當一次的端點和當其他次的中間點。端點只會和1個點連線，選擇只需扣1。中間點一定會和左右兩點連線。中間點必須扣2。當端點 5 - 1 = 4 當中間點 4 - 2 = 2 當另一次的中間點 2 - 2 = 0 點1是這樣，同理點2 ~ 點6也是這樣，每個點的結果都會剛好是0。所以當端點的一次 + 當中間點的兩次 = 3 n / 2是這樣來的。 Bleed ============================================================================== 以6個點為例。 1 - 2 - 3 - 4 - 5 - 6 目前的關係 / 剩下的連接選擇 2 - 1 3, 4, 5, 6 1 - 2 4, 5, 6 3 - 2 2 - 3 1, 5, 6 4 - 3 3 - 4 1, 2, 6 5 - 4 4 - 5 1, 2, 3 6 - 5 5 - 6 1, 2, 3, 4 1. 如果不是端點，而是中間點，一定會連到兩個點。 2. 一次只有兩個端點。 3. 2, 3, 4, 5 各有1次中間點和1次端點的機會。 1, 6 都是中間點。(因為123456的1,6已經當過端點了) 所以只能有3個解(兩次的解加原本的123456)。為什麼只能有1次端點的機會。以上表來說, 3剩下1, 5, 6連接選擇, 4剩下1, 2, 6連接選擇。端點只會去掉一個點。所以3和4變成會有3個次當端點的機會。 3,4都是端點代表其他點都是中間點，都要一次扣2個點。就算是最多選擇的1和6也只有4個點，不夠扣3次。而2和5只有3個點，連2次都不能扣到。所以至多只有1次端點的機會。 Bleed ========================================================= 作者: bleed1979 (十三) 看板: C_and_CPP 標題: Re: [ACM ] 11597-Spanning Subtree 時間: Mon Apr 5 17:10:56 2010 ※ 引述《jason3e7 (小綠)》之銘言： : 題號：11597 : 遇到的問題：題目看不懂? 不知道實際上那樹長什麼樣子 : 附上中文題目跟英文題目的連結 : 中文：http://zerojudge.tw/ShowProblem?problemid=d656 : 英文： : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2644 這題... 我的理解是這樣的。找2個spanning subtree，這兩個spanning subtree彼此沒有連通的邊。所以4個點可以是解1: (1個點形成的subtree, 3個點形成的subtree) 解2: (2個點形成的subtree, 2個點形成的subtree) 所以總共2個解。同樣的，6個點可以是 1. (1,5) 2. (2,4) 3. (3,3) 所以是3個解。算到400你會發現一件很恐怖的事。好，這題講解完了，就這樣。 Bleed -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.32.177.97

→

YesIam118

04/05 18:29, , 1^F

04/05 18:29, 1^F

→

YesIam118

04/05 18:31, , 2^F

04/05 18:31, 2^F

推

seedman

04/06 01:04, , 3^F

04/06 01:04, 3^F