1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<map> 9 #include<iomanip>10 #define INF 9999999911 using namespace std;12 13 const int MAX = 15 + 5;14 int edge[MAX][MAX], dist[MAX], node[MAX];//node记录最终选的点 15 int vale[MAX], temp[MAX], n, m;//temp记录选的m个点16 double minratio;17 bool mark[MAX];18 19 int Prim(int s){20     int sum = 0;21     for (int i = 1; i <= m; ++i)mark[temp[i]] = false, dist[temp[i]] = edge[s][temp[i]];22     mark[s] = true;23     dist[s] = 0;24     for (int i = 1; i<m; ++i){25         int point = s;26         for (int j = 1; j <= m; ++j){27             if (point == s && !mark[temp[j]])point = temp[j];28             if (!mark[temp[j]] && dist[point]>dist[temp[j]])point = temp[j];29         }30         mark[point] = true;31         sum += dist[point];32         for (int j = 1; j <= m; ++j){33             if (!mark[temp[j]] && edge[point][temp[j]]<dist[temp[j]])dist[temp[j]] = edge[point][temp[j]];34         }35     }36     return sum;37 }38 39 void dfs(int u, int num){40     if (num == m){41         int ans = 0;42         for (int i = 1; i <= m; ++i)ans += vale[temp[i]];43         double sum = Prim(u)*1.0 / ans;44         if (sum - minratio < -(1e-9)){45             minratio = sum;46             for (int i = 1; i <= m; ++i) node[i] = temp[i];47         }48         return;49     }50     if (n - u + num<m)return;51     for (int i = u + 1; i <= n; ++i){52         temp[num + 1] = i;53         dfs(i, num + 1);54     }55 }56 57 int main(){58     while (cin >> n >> m, n + m){59         minratio = INF*1.0;60         for (int i = 1; i <= n; ++i)cin >> vale[i];61         for (int i = 1; i <= n; ++i){62             for (int j = 1; j <= n; ++j){63                 cin >> edge[i][j];64             }65         }66         for (int i = 1; i <= n; ++i){67             temp[1] = i;68             dfs(i, 1);69         }70         for (int i = 1; i<m; ++i)cout << node[i] << ‘ ‘;71         cout << node[m] << endl;72     }73     return 0;74 }

 1 //调用时：dfs(1,0,0); 2  3 //dep表示点的编号，cnt表示选取的点的个数，sum_pw表示目前选取了cnt个点后总的点权值 4 void dfs(int dep, int cnt, int sum_pw) { 5     if(cnt == m) { 6         ...; 7         return ; 8     } 9     if(dep == n + 1) return ;10     use[dep] = true;  //选取点dep，这里use[i]=true表示选取点i，在用prim求最小生成树的时候有用11     dfs(dep + 1, cnt + 1, sum_pw + weight[dep]);12     use[dep] = false; //不选取点dep13     dfs(dep + 1, cnt, sum_pw);14 }