先用DFS求出全组合，然后每个组合求最小生成树。
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; int n, m, summ; int u[10000][20]; int t[20], ff[20], nodecost[20], father[20]; int edgecost[20][20]; struct abc{ int start, end, cost; }node[20 * 20]; int find(int x) { if (x != father[x]) father[x] = find(father[x]); return father[x]; } void dfs(int tot, int i) { int j; if (tot == m){ for (j = 0; j < m; j++) u[summ][j] = t[j]; summ++; return; } if (i > n) return; t[tot] = i; dfs(tot + 1, i + 1); dfs(tot, i + 1); } bool cmp(const abc&a, const abc&b){ return a.cost < b.cost; } int main() { int i, j, ii; while (~scanf("%d%d", &n, &m)) { if (n == 0 && m == 0) break; summ = 0; dfs(0, 1);//DFS生成全组合 for (i = 1; i <= n; i++) scanf("%d", &nodecost[i]); for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) scanf("%d", &edgecost[i][j]); int sx = 0; for (i = 1; i <= n; i++) { for (j = i + 1; j <= n; j++) { node[sx].start = i; node[sx].end = j; node[sx].cost = edgecost[i][j]; sx++; } } sort(node, node + sx, cmp); double minratio = 999999999; int edge_weight, node_weight, anss; for (ii = 0; ii < summ; ii++) { memset(ff, 0, sizeof(ff)); edge_weight = 0, node_weight = 0; for (i = 0; i <= n; i++) father[i] = i; for (i = 0; i < m; i++) ff[u[ii][i]] = 1, node_weight = node_weight + nodecost[u[ii][i]]; for (i = 0; i < sx; i++) { if (ff[node[i].start] && ff[node[i].end]) { int x = find(node[i].start); int y = find(node[i].end); if (x != y) { father[x] = y; edge_weight = edge_weight + node[i].cost; } } } if (1.0*edge_weight / node_weight < minratio) minratio = 1.0*edge_weight / node_weight, anss = ii; } for (i = 0; i < m; i++) { if (i < m - 1) printf("%d ", u[anss][i]); else if (i == m - 1) printf("%d ", u[anss][i]); } } return 0; }