hdu 2489(枚举 + 最小生成树)

时间:2022-05-20 08:25:55

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2489

思路:由于N, M的范围比较少,直接枚举所有的可能情况,然后求MST判断即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std; const int MAX_N = 17;
const double eps = 1e-10;
struct Edge {
int u, v, w;
Edge() {}
Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
} edge[MAX_N * MAX_N]; int cmp(const Edge &e1, const Edge &e2)
{
return e1.w < e2.w;
} int N, M, cnt, weight[MAX_N], g[MAX_N][MAX_N];
int parent[MAX_N];
void Init()
{
for (int i = 0; i < N; ++i) parent[i] = i;
} int find(int x)
{
if (x == parent[x]) return x; return parent[x] = find(parent[x]);
} void Union(int u, int v)
{
int r1 = find(u), r2 = find(v);
if (r1 == r2) return; parent[r1] = r2;
} double res;
vector<int > tmp, ans;
bool vis[MAX_N];
void gao(int state)
{
tmp.clear();
memset(vis, false, sizeof(vis));
int a = 0, b = 0;
for (int i = 0; i < N; ++i) {
if ((1 << i) & state) tmp.push_back(i), b += weight[i], vis[i] = true;
} Init();
for (int i = 0; i < cnt; ++i) {
Edge e = edge[i];
if (vis[e.u] && vis[e.v]) {
if (find(e.u) != find(e.v)) {
Union(e.u, e.v);
a += e.w;
}
}
} if (res < eps) {
res = a * 1.0 / b;
ans = tmp;
} else if (a * 1.0 / b + eps < res) {
res = a * 1.0 / b;
ans = tmp;
} else if (fabs(a * 1.0 / b - res) < eps) {
bool tag = false;
for (int i = 0; i < (int)ans.size(); ++i) {
if (ans[i] > tmp[i]) { tag = true; break; }
} if (tag) ans = tmp;
} } int main()
{
while (~scanf("%d %d", &N, &M)) {
if (N == 0 && M == 0) break; for (int i = 0; i < N; ++i) scanf("%d", &weight[i]);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) scanf("%d", &g[i][j]);
} cnt = 0;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) edge[cnt++] = Edge(i, j, g[i][j]);
} sort(edge, edge + cnt, cmp);
res = 0.0;
ans.clear();
for (int s = 0; s < (1 << N); ++s) {
int x = s, n = 0;
while (x) {
++n;
x &= (x - 1);
} if (n == M) {
gao(s);
}
} for (int i = 0; i < (int)ans.size(); ++i) {
printf(i == 0 ? "%d" : " %d", ans[i] + 1);
}
puts(""); }
return 0;
}