题意：给出一个图 n x n (2<=n<=15)的图，每个点，每条边都有权值，求其中的 m (2<=m<=n)个点，使得这m个点生成的树的边点权比例最小。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2489
——>>数量小，于是，可以枚举取 m 个点的所有情况，对每种情况最一次MST，更新最小值。。
时间复杂度：O(n ^ n * log(n) * 2 ^ n)
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>using std::priority_queue;const int MAXN = 15;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;struct EDGE
{int from;int to;int w;EDGE() {}EDGE(int from, int to, int w) : from(from), to(to), w(w) {}bool operator < (const EDGE& e) const{return w > e.w;}
};int n, m;
int sume, sumn;
int node[MAXN];
int G[MAXN][MAXN];
int toUse[MAXN], ucnt;
int fa[MAXN];void Init()
{sume = 0;sumn = 0;
}int Find(int x)
{return x == fa[x] ? x : (fa[x] = Find(fa[x]));
}void Union(int x, int y)
{int xroot = Find(x);int yroot = Find(y);if (xroot != yroot){fa[yroot] = xroot;sume += G[x][y];}
}void Read()
{for (int i = 0; i < n; ++i){scanf("%d", node + i);}for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){scanf("%d", &G[i][j]);}}
}int Ones(int x)
{int ret = 0;while (x){if (x & 1){++ret;}x >>= 1;}return ret;
}void GetUseNode(int S)
{ucnt = 0;for (int j = 0; (1 << j) <= S; ++j){if ((1 << j) & S){toUse[ucnt++] = j;sumn += node[j];}}
}void InitUnion()
{for (int j = 0; j < n; ++j){fa[j] = j;}
}void Kruscal()
{priority_queue<EDGE> pq;for (int j = 0; j < ucnt; ++j){for (int k = j + 1; k < ucnt; ++k){pq.push(EDGE(toUse[j], toUse[k], G[toUse[j]][toUse[k]]));}}while (!pq.empty()){EDGE e = pq.top();pq.pop();Union(e.from, e.to);}
}void Output(int ret)
{bool fst = true;for (int i = 0; (1 << i) <= ret; ++i){if ((1 << i) & ret){if (fst){fst = !fst;}else{putchar(' ');}printf("%d", i + 1);}}puts("");
}int Dcmp(double x)
{if (fabs(x) < EPS) return 0;return x > 0 ? 1 : -1;
}void Solve()
{int ret = 0;double Min = INF;for (int i = 3; i < (1 << n); ++i){if (Ones(i) != m) continue;Init();GetUseNode(i);InitUnion();Kruscal();double r = (double)sume / sumn;if (Dcmp(r - Min) < 0){Min = r;ret = i;}}Output(ret);
}int main()
{while (scanf("%d%d", &n, &m) == 2){if (!n && !m) break;Read();Solve();}return 0;
}