討論串[問題] ACM UVa10160 Servicing Station
共 5 篇文章
內容預覽:
小弟online judge在這題卡住了 : Problem D: Servicing stations. 這題是給一群city 還有一堆city之間的connection. 然侯要找出能cover所有city的. service station的最小數目. 一個station可以服務所在地的所有i
(還有168個字)
內容預覽:
還是TLE. @_@ vertex cover那個好難 現在看不是很懂.....XD. 小弟我的做法大概是:. BackTrack. 1. 檢查現在的station數目 比之前的所有解的最小數目還大的話 就return. 2. 產生可能的candidate list:. A. 對所有還沒有被服務到的
(還有213個字)
內容預覽:
嗯，我把實作su版友所提示的方法詳述。. 1.審題：. 這個問題我想成是所有點著色，可選擇黑或白兩種顏色。. 黑色是關鍵點，其鄰居是白色。. 這題就變成最少的黑色點是多少個可以涵蓋所有點且符合題意。. 2.資料結構：. 2.1 顏色. 您需要三種狀態。尚未塗色，黑色和白色三種。. const int
(還有1513個字)
內容預覽:
抱歉回文回得有點慢.... 我用的方法是backtracking. 窮舉n個0/1數字的所有排列. （類似於窮舉所有子集合）. 遞迴過程當中. 甲、隨時計算目前被服務到的城市有哪些. 乙、也隨時判斷目前的排列是不是合理的. 丙、也隨時紀錄目前的最佳解！可以做bound！. 因為這題的n值有點大. 所
(還有621個字)
內容預覽:
感謝各位先進的鼎力相助 我已經AC了 雖然還是需要1.3秒 ORZ. 解法大概上就是跟各位講述的差不多 那來個quantitive的亂分析好了. 我之前的解法:. Backtrack的順序是跟 graph search接近, 先從city1出發, 當作第一個服務站, 找跟. city1相連的的cit
(還有340個字)