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

Re: [問題] ACM UVa10160 Servicing Station

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間14年前 (2010/10/04 02:37)推噓1(1推 0噓 7→)

留言8則, 1人參與討論串3/5 (看更多)

嗯，我把實作su版友所提示的方法詳述。 1.審題：這個問題我想成是所有點著色，可選擇黑或白兩種顏色。黑色是關鍵點，其鄰居是白色。這題就變成最少的黑色點是多少個可以涵蓋所有點且符合題意。 2.資料結構： 2.1 顏色您需要三種狀態。尚未塗色，黑色和白色三種。 const int NO_COLOR = 0, BLACK = 1, WHITE = 2; 2.2 每個點所代表顏色。您需要一個大小符合測資限制的一維陣列。 int town_color[36]; // 值就是2.1的那三種 2.3 每個點的相鄰點有那些？您需要的是一個大小符合測資限制的二維陣列或容器。 bool conn[36][36]; // 相鄰的點為true，否則為false 或 vector<int> conn[36]; // 每個vector存放相鄰點的index 2.4 點數有幾個，pair有幾個，最少的黑色點數有幾個 int t; int p; int min_town_black; // 隨意舉例，請自行取名 3.實作 3.1 初始化和檢查沒有鄰居的點，將其著色為黑色， 3.1.1 初始化，略 3.1.2 for迴圈檢查沒有鄰居的點，著黑色。 for(int i = 1; i <= t; ++i) 如果點i沒有鄰居 town_color[i] = BLACK; 3.2 backtracking或dfs遞迴過程中，合法和不合法的情況。一個函式legal()，合法回傳true，不合法回傳false 3.2.1 不合法遍搜所有點，如果有某個點是白色並且其相鄰所有點都已經著色過，這些相鄰點也都是白色，顯然這某個點為不合法。 3.2.2 合法遍搜過所有點後，都不會是3.2.1，那就是合法。至此得到架構 bool legal() { for(int i = 1; i <= 所有點; ++i) 如果點i是白色如果點i的所有鄰居都是白色 return false; return true; } dfs() { if(legal()) { // do something; } } 3.3 終止backtracking和dfs的時候跑dfs，從第1個點著色到第n點，當索引跑到n + 1為終止。終止時記錄最少黑色點數。得到架構 // x 是目前著色的點 // t 是總共幾個點 // b 是已經有幾個點著黑色 dfs(int x, int t, int b) { if(legal(t)) { if(x > t) min_town_black = b; else { // do something, 3.4 和 3.5 } } } 3.4 對於每個點x，何時著黑色與其動作 3.4.1 如果點x不是白色(已經著黑色或是尚未著色)，那就著黑色，跑遞迴。 3.4.2 或是，如果點x的鄰居尚未著色，那就著黑色，跑遞迴。 3.4.3 b + 1 < min_town_black 3.4.4 動作 3.4.4.1 紀錄此時此刻著色的town_color 3.4.4.2 將點x著黑色，town_color[x] = BLACK; 3.4.4.3 如果點x的鄰居尚未著色，著白色。 3.4.4.4 跑遞迴。dfs(x + 1, t, b + 1); 3.4.4.5 還原town_color 3.5 對於每個點x，何時著白色與其動作 3.5.1 如果點x至少有一個以上的鄰居 3.5.2 b < min_town_black 3.5.3 動作 3.5.3.1 紀錄此時此刻著色的town_color 3.5.3.2 將點x著白色，town_color[x] = WHITE; 3.5.3.3 跑遞迴。dfs(x + 1, t, b); 3.5.3.4 還原town_color 3.6 輸出min_town_black，結束。 Bleed ※ 引述《rifiz (薩哈拉雅)》之銘言： : ※ 引述《rifiz (薩哈拉雅)》之銘言： : : 小弟online judge在這題卡住了 : Problem D: Servicing stations : : 這題是給一群city 還有一堆city之間的connection. 然侯要找出能cover所有city的 : : service station的最小數目. 一個station可以服務所在地的所有immediate city. : : 我使用的方法是 backtracking, 也就是暴力法的一種. 這種方法的精華應該是在 : : 剪枝但是我沒辦法減到足夠少的狀態數目有誰可以給個建議要如何減少才行嗎? : : 目前我的剪枝只有: 比上一次的數目多的話就不搜尋了 XD : : 請先進給我一點想法跟意見阿.......感激不盡 : : -------------------- : : 已經TLE好幾百次了 @_@ : 還是TLE. @_@ vertex cover那個好難現在看不是很懂.....XD : 小弟我的做法大概是: : BackTrack : 1. 檢查現在的station數目比之前的所有解的最小數目還大的話就return : 2. 產生可能的candidate list: : A. 對所有還沒有被服務到的city, check: : 這個city所連出去的的city是不是至少有一個還沒被服務到, 是的話才加入 : candidate list. : 3. For each candidate: : A. append到solution list的尾端 : B. 把被他服務到的city mark起來 : C. BackTracking. : 有試過如下的剪枝: : 每次選擇的點所造成的cover set每一步都要 > 上一次的每一步的cover set, 可是這樣 : 會錯(事實上也找的出反例 XD) : 但是上面這樣的剪枝應該還是不夠, 看了各位大大的建議只能得出上面的做法..... : 請幫忙再建議一下該如何在哪裡剪枝...... : 謝謝各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.25.243.17