看板 [ Prob_Solve ]
討論串[討論] UVa12615
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[討論] UVa12615
推噓8(8推 0噓 13→)留言21則，0人參與, 最新作者dreamoon (大笨蛋小月唷!)時間10年前 (2015/01/15 03:37), 編輯資訊
1
0
2
內容預覽:
想試著和大家討論看看題目 >_<. http://uva.onlinejudge.org/external/126/12615.html. 這題是這樣的，有一個Graph,每條邊都有cost. 它滿足四個條件:. 1. 此圖為連通圖. 2. 每個點degree至多6. 3. 此圖上若有cycle，則
(還有1510個字)
#2
Re: [討論] UVa12615
推噓3(3推 0噓 5→)留言8則，0人參與, 最新作者DJWS (...)時間10年前 (2015/01/15 22:54), 9年前編輯資訊
1
0
0
內容預覽:
原題我不會解，不過我可以解釋一下支配集和獨立集. 獨立集(independent set)：選出一些點，互不相鄰。. 最佳化問題是越多越好。. 支配集(dominating set)：選出一些點，其餘點皆與之相鄰（所有點皆與之相鄰/重疊）。. 最佳化問題是越少越好。. 這兩個都是NP-complet
(還有778個字)
#3
Re: [討論] UVa12615
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者FRAXIS (喔喔)時間10年前 (2015/01/16 01:18), 編輯資訊
1
0
1
內容預覽:
其實 minimum edge dominating set 的大小是跟. minimum independent edge dominating set 是一樣的. 然後 minimum independent edge dominating set 是一個. minimum maximal ma
(還有92個字)
#4
Re: [討論] UVa12615
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者DJWS (...)時間9年前 (2015/01/16 11:12), 9年前編輯資訊
0
0
1
內容預覽:
我前面有一句話有錯：. 極大獨立集 = 極小支配集 這句話有錯. 這是單向不是雙向。. 1. 極大獨立集，必是極小支配集。. 2. 極小支配集，不一定是(極小)獨立集。支配集的點可以相鄰，不一定要獨立。. 然後你現在提到的是新概念：. 獨立支配集(independent dominating set
(還有297個字)
首頁
上一頁
1
下一頁
尾頁