首页 > 代码库 > hdu - 2489 - Minimal Ratio Tree(枚举 + MST)
hdu - 2489 - Minimal Ratio Tree(枚举 + MST)
题意:给出一个图 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; }
hdu - 2489 - Minimal Ratio Tree(枚举 + MST)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。