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