PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] ACM UVa10160 Servicing Station

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間14年前 (2010/10/14 18:00)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串4/5 (看更多)

抱歉回文回得有點慢... 我用的方法是backtracking 窮舉n個0/1數字的所有排列（類似於窮舉所有子集合）遞迴過程當中甲、隨時計算目前被服務到的城市有哪些乙、也隨時判斷目前的排列是不是合理的丙、也隨時紀錄目前的最佳解！可以做bound！因為這題的n值有點大所以我用了一些小技巧來避免TLE 一、紀錄地圖的資料結構我用的是adjacency lists 這樣可以節省一點時間二、紀錄城市有被/沒被服務我用了一個類似於counting sort的陣列如果城市x有被服務到　就count[x]++; 如果城市沒被服務到就不加加這樣可以節省一點時間程式碼也會變得很優雅三、一開始我先把每個城市都放上服務站把count[x]統統累加好執行回溯法的時候則是使用消去/不消去服務站兩種選擇這樣子倒行逆施有一個好處就是每當發現有一個城市沒有被服務到（count[x] <= 0）馬上就可以剪枝！四、我用了一個bound 當遞迴到第m層時第1~m的城市共留有c個服務站此時如果把m+1~n的服務站全部去掉之後發現沒有比最佳解好到哪裡去（c - (n-m) >= ans）就算繼續遞迴下去也沒意義馬上就可以bound！（這個不是A*喔...就是branch and bound的bound！）我用的方法大致上是這樣如果有需要我再寄程式碼給你，不用客氣！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.115.153.221 ※ 編輯: DJWS 來自: 59.115.153.221 (10/14 18:04) ※ 編輯: DJWS 來自: 59.115.153.221 (10/14 18:05) ※ 編輯: DJWS 來自: 59.115.153.221 (10/14 18:11) ※ 編輯: DJWS 來自: 59.115.153.221 (10/14 18:16)