这题不会。还以为有什么方法能直接搞出来最小的ratio以及那些点，结果就是枚举，不过就算是枚举我也写不出来啊~
dfs选择m个点，而且更重要的是 不是中途选够了m个点就怎么样怎么样，而是必须搞到最后一层，这样select的值才完备了，所以中间可以剪枝，比如如果选了m+1个点就可以直接return了，比如如果现在已选的加上接下来都选也达不到m也可以return了（这个没实现）。 而且这个dfs写法有讲究的是从1开始先选再不选，所以这样可以保证如果多个最小值，被赋给ans的肯定是字典序最小的。 所以到最后一层就有 Cmn 个结果，所以就挨个prim（部分点求mst）呗，看看谁更小。 #include#include #include #include using namespace std;const int INF = 1e9;const int MAXN = 15 + 1;int N, M;int weight[MAXN];int g[MAXN][MAXN];bool select[MAXN];bool ans[MAXN];double opt;double prim() // 求部分点的最小生成树，反正题目是完全图，总能找到边{ int node_sum = 0; int edge_sum = 0; int d[MAXN]; bool vis[MAXN]; bool first = 0; for (int i = 1; i <= N; i++) { if (select[i]) { node_sum += weight[i]; d[i] = INF; vis[i] = 0; if (!first) { d[i] = 0; first = 1; } } } for (int i = 0; i < M; i++) { int mind = INF, u = -1; for (int j = 1; j <= N; j++) { if (select[j] && !vis[j] && d[j] < mind) { mind = d[j]; u = j; } } vis[u] = 1; edge_sum += mind; for (int j = 1; j <= N; j++) if (select[j] && !vis[j] && g[u][j] < d[j]) d[j] = g[u][j]; } return (double)edge_sum / (double)node_sum;}void dfs(int v, int num) // 从n个里面选m个，虽然 Cn(m) < 2^n ，但是2^n的写法简单，而且这里n就15{ if (num > M) return; // 剪枝 if (v == N + 1) // 必须逛到最后一层才能计算结果，即使在前面已经选择满了 { if (num == M) { double t = prim(); if (t < opt) { opt = t; memcpy(ans, select, sizeof ans); // 这两个数组长度一样 } } return; } select[v] = 1; // 这样的展开次序可以保证最终答案字典序最小 dfs(v + 1, num + 1); select[v] = 0; dfs(v + 1, num);}int main(){ for (; ~scanf("%d%d", &N, &M);) { if (!N) break; opt = INF; for (int i = 1; i <= N; i++) scanf("%d", &weight[i]); for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) scanf("%d", &g[i][j]); dfs(1, 0); bool first = 0; for (int i = 1; i <= N; i++) { if (ans[i]) { if (first) printf(" "); printf("%d", i); first = 1; } } printf("\n"); } return 0;}