借圖用一下
１ ２ １ ２ １ ２
●─● ●─● ● ●
│╳│ ＝ ／ ∪ │＼│
●─● ●─● ● ●
３ ４ ３ ４ ３ ４
產生的數列
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:spanning subtree的定義不是每個點都要有連到嗎? 04/05 18:29
→ YesIam118:你舉的例子怪怪的 04/05 18:31
推 seedman:你的講解連same input都是錯的阿 XD 04/06 01:04
→ bleed1979:輸入4得2解，輸入6得3解，這題輸出就是n/2。 04/06 04:25
→ bleed1979:我想請問樓上兩位有那個是真的有send程式上去的。 04/06 04:26
→ bleed1979:我不敢說我的理解是對的，但我以我AC的想法來解釋。 04/06 04:26
推 LPH66:上一篇推文的 suhorng 應該是對的... 04/06 06:47
→ YesIam118:當然有AC囉 一看就知道答案是N/2 但重點在為什麼呢? 04/06 08:35
※ 編輯: bleed1979 來自: 114.32.177.97 (04/06 09:11)
→ bleed1979:原文已經增加篇幅。 04/06 09:12
※ 編輯: bleed1979 來自: 114.32.177.97 (04/06 10:12)
推 AstralBrain:你對題目的認知有點問題.. 04/06 13:38
推 AstralBrain:樓下LPH的解釋是對的 04/06 13:42
→ bleed1979:也許你對我解釋的認知有點問題。 04/06 14:48
※ 編輯: bleed1979 來自: 114.32.177.97 (04/06 15:39)
推 AstralBrain:你的spanning tree只有一直線的嗎 04/06 15:45
→ bleed1979:4個點為例，1連4，2連4和3連4這樣嗎？ 04/06 15:55
推 AstralBrain:中間那個六個點的例子 04/06 15:55
→ AstralBrain:剩下的邊是(1,2)(1,3)(1,4)(3,5)(2,6) 04/06 15:55
→ AstralBrain:這樣也是spanning tree 04/06 15:56
→ bleed1979:6個點。1-2-3-4-5-6, 4-1-5-2-6-3, 5-3-1-6-4-2 04/06 15:59
→ bleed1979:請一個月內用任何方法舉出不與上述重複邊的生成樹。 04/06 16:00
推 AstralBrain:你都把邊用完了是要找什麼= = 04/06 16:03
→ AstralBrain:我沒說n/2不對喔 我是說解釋不對 04/06 16:03
→ bleed1979:只是覺得鑽生成樹不唯一的漏洞很無聊，討論是點和點連。 04/06 16:09
推 AstralBrain:誰在鑽漏洞了 04/06 16:10
→ AstralBrain:就說K6扣掉1-6-5-4-3-2和3-6-4-2-5-1後還是生成樹了 04/06 16:11
→ AstralBrain:你自己沒有考慮到其他的情況 04/06 16:11
推 AstralBrain:工作結束 回來多講一點.. 04/06 18:40
→ AstralBrain:你只說了這n/2條path的端點必需相異 04/06 18:41
→ AstralBrain:然後呢? n很大的時候一定可以構造出不重複的path嗎 04/06 18:41
→ AstralBrain:這樣根本什麼都沒有說明啊 04/06 18:42