嗯，我把實作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