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; }