参考链接：http://blog.csdn.net/xingyeyongheng/article/details/9373271
http://www.cnblogs.com/chenxiwenruo/p/3294668.html
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 99999999 11 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 dfs枚举m个点，num代表目前选取了多少个点，k代表第num个点为k。 40 表示前num个点选自1~k，剩余的点从k+1~n中选。 41 */ 42 void dfs(int u, int num){ 43 if (num == m){ 44 int ans = 0; 45 for (int i = 1; i <= m; ++i)ans += vale[temp[i]]; 46 double sum = Prim(u)*1.0 / ans; 47 if (sum - minratio < -(1e-9)){ 48 minratio = sum; 49 for (int i = 1; i <= m; ++i) node[i] = temp[i]; 50 } 51 return; 52 } 53 //若剩余的点的个数(n-k)加上目前选取的个数num小于m的话，说明即使接下来n-k个点都选取，也选不足m个点，直接return 54 if (n - u + num<m)return; 55 for (int i = u + 1; i <= n; ++i){ 56 temp[num + 1] = i; 57 dfs(i, num + 1); 58 } 59 } 60 61 int main(){ 62 while (cin >> n >> m, n + m){ 63 minratio = INF*1.0; 64 for (int i = 1; i <= n; ++i)cin >> vale[i]; 65 for (int i = 1; i <= n; ++i){ 66 for (int j = 1; j <= n; ++j){ 67 cin >> edge[i][j]; 68 } 69 } 70 for (int i = 1; i <= n; ++i){ 71 temp[1] = i; 72 dfs(i, 1); 73 } 74 for (int i = 1; i<m; ++i)cout << node[i] << ' '; 75 cout << node[m] << endl; 76 } 77 return 0; 78 }
别的大牛DFS写法
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; //不选取点dep 13 dfs(dep + 1, cnt, sum_pw); 14 }