迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 3:53 PM
Orz MST寫出來了但是不知道要跑多久所以不知道有沒有錯T^T
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 3:55 PM
部分CODE
我覺得我實作的地方應該是沒錯...吧?
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 3:56 PM
這個作業決定我被當與否XDDDD((不調分的情況下
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 3:56 PM
未命名大大快救我
未命名（Ｇｙａｏｏ！）
@boy69162000
說
Sat, Jun 22, 2013 3:59 PM
奇怪 你不是吳育松嗎lol
未命名（Ｇｙａｏｏ！）
@boy69162000
說
Sat, Jun 22, 2013 4:02 PM
所以你現在只要求結果正確就好吧?
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:03 PM
未命名（Ｇｙａｏｏ！） : 對
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:03 PM
就算結果不對 只要三個測資過就好 但是與其這樣還不如直接結果對QQ
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:04 PM
我是把點全部放入list 然後按照weight去排大小 然後從最小的全部看一遍
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:05 PM
*把Edge(u,v,w)放入list
未命名（Ｇｙａｏｏ！）
@boy69162000
說
Sat, Jun 22, 2013 4:05 PM
就Kruskal吧
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:05 PM
這應該算...那個什麼kal的(prim的另一個)
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:05 PM
嗯嗯對
未命名（Ｇｙａｏｏ！）
@boy69162000
說
Sat, Jun 22, 2013 4:06 PM
重點就是你要確定有沒有形成cycle
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:07 PM
反正最終結果就是每個點都會最少有一個Edge連接吧
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:08 PM
我是這樣想 如果看一個已經sort好的Edge
那每個Edge會有5種可能
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:08 PM
1.u點已經連接 v點沒有
2.v點已經連接 u點沒有
這兩個只要直接連上去就好了
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:09 PM
3.u點和v點已經連接 但是已透過其他線連接(屬於同一個(group)
忽略這條線
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:10 PM
4.u點和v點都沒連接
連接起來 並新增一個group存放
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:10 PM
5.u點和v點已經連接 但是未透過其他線連接(屬於不同group)
兩點連接 並統合兩group為一個
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:10 PM
應該就這五種可能 不知道我想法有沒有錯?
未命名（Ｇｙａｏｏ！）
@boy69162000
說
Sat, Jun 22, 2013 4:13 PM
理論上是這樣沒錯
迪恩‧凡爾賽提斯
@tony4794
Sat, Jun 22, 2013 4:20 PM
好吧 只好先跑跑看了><
((∑[T𝒰]∏A∈T]A≃1
@suhorng
Sat, Jun 22, 2013 4:25 PM
為什麼不用disjoint set...?
((∑[T𝒰]∏A∈T]A≃1
@suhorng
Sat, Jun 22, 2013 4:26 PM
只要這條邊連接的兩個點不在同一個set中, 就union起來就好 @@
未命名（Ｇｙａｏｏ！）
@boy69162000
說
Sat, Jun 22, 2013 4:33 PM
((∑[T𝒰]∏A∈T]A≃1 : 小黃也是要我們這樣做 結果我把disjoint set睡掉 根本不懂他的要求是啥毀
未命名（Ｇｙａｏｏ！）
@boy69162000
說
Sat, Jun 22, 2013 4:34 PM
XD 所以只好暴力走tree搜cycle
Knife
@LauZi
Sat, Jun 22, 2013 4:39 PM
disjoint set 不好嗎，又快又好寫又好懂
((∑[T𝒰]∏A∈T]A≃1
@suhorng
Sat, Jun 22, 2013 4:46 PM
ideone.com/V91EtA 沒測過, 小心服用
((∑[T𝒰]∏A∈T]A≃1
@suhorng
Sat, Jun 22, 2013 4:48 PM
pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=fc22d13342f3c9b0b436180bc9706557bf988804b Lesson 2 Section 7, 那張圖說明一切
迪恩‧凡爾賽提斯
@tony4794
Wed, Jul 3, 2013 4:29 PM
啊啊後來沒看到 不過還是謝了
迪恩‧凡爾賽提斯
@tony4794
Wed, Jul 3, 2013 4:29 PM
最後還好有及格
載入新的回覆