POJ 3925 Minimal Ratio Tree（枚举+最小生成树）

本文主要是介绍POJ 3925 Minimal Ratio Tree（枚举+最小生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

POJ 3925 Minimal Ratio Tree

题目链接

题意：给定一些点权和一个边权矩阵，求一个最小的比例的树

思路：先枚举用哪些点，然后求最小生成树即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 20;int n, m, val[N], edge[N][N];int bitcount(int x) {if (x == 0) return 0;return bitcount(x>>1) + (x&1);
}struct Edge {int u, v, w;Edge() {}Edge(int u, int v, int w) {this->u = u;this->v = v;this->w = w;}
} e[N * N];int en;bool cmp(Edge a, Edge b) {return a.w < b.w;
}int parent[N];int find(int x) {return x == parent[x] ? x : parent[x] = find(parent[x]);
}int cal() {sort(e, e + en, cmp);for (int i = 0; i < n; i++) parent[i] = i;int tot = n;int ans = 0;for (int i = 0; i < en; i++) {int pu = find(e[i].u);int pv = find(e[i].v);if (pu != pv) {parent[pu] = pv;ans += e[i].w;tot--;}if (tot == 1) break;}return ans;
}int main() {while (~scanf("%d%d", &n, &m) && n || m) {for (int i = 0; i < n; i++) scanf("%d", &val[i]);for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)scanf("%d", &edge[i][j]);int maxs = (1<<n);int anss;double ans = 1e15;for (int i = 1; i < maxs; i++) {if (bitcount(i) != m) continue;int sumnode = 0;en = 0;for (int u = 0; u < n; u++) {if (i&(1<<u)) {sumnode += val[u];for (int v = 0; v < n; v++) {if (edge[u][v] == 0) continue;if (i&(1<<v)) e[en++] = Edge(u, v, edge[u][v]);}}}double tmp = cal() * 1.0 / sumnode;if (ans > tmp) {ans = tmp;anss = i;}}int bo = 0;for (int i = 0; i < n; i++) {if (anss&(1<<i)) {if (bo) printf(" ");else bo = 1;printf("%d", i + 1);}}printf("\n");}return 0;
}

这篇关于POJ 3925 Minimal Ratio Tree（枚举+最小生成树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---