本文主要是介绍hdu 2489 (dfs枚举 + prim)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
对于一棵顶点和边都有权值的树，使用下面的等式来计算Ratio
给定一个n 个顶点的完全图及它所有顶点和边的权值，找到一个该图含有m 个顶点的子图，并且让这个子图的Ratio 值在所有m 个顶点的树中最小。
解析：
因为数据量不大，先用dfs枚举搭配出m个子节点，算出点和，然后套个prim算出边和，每次比较大小即可。
dfs没有写好，A的老泪纵横。
错在把index在dfs过程中处理，在递归口处理更直观也更易于理解。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 15 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);int n, m;
int nodeWeight[maxn];
int edgeWeight[maxn][maxn];
int ans[maxn], index[maxn];
int g[maxn][maxn];int prim()
{bool vis[maxn];int dis[maxn];memset(vis, false, sizeof(vis));memset(dis, inf, sizeof(dis));vis[1] = true;dis[1] = 0;int res = 0;int mark = 1;for (int i = 1; i <= m - 1; i++){for (int j = 1; j <= m; j++){if (!vis[j] && g[mark][j] < dis[j])dis[j] = g[mark][j];}int mindis = inf;for (int j = 1; j <= m; j++){if (!vis[j] && dis[j] < mindis){mindis = dis[j];mark = j;}}vis[mark] = true;res += mindis;}return res;
}double minn;
void dfs(int cur, int dep)
{index[dep] = cur;if (m == dep){///开始没处理好for (int i = 1; i <= m; i++){for (int j = 1; j <= m; j++){g[i][j] = edgeWeight[index[i]][index[j]];}}///int mu = prim();double zi = 0.0;for (int i = 1; i <= m; i++){zi += nodeWeight[index[i]];}if (mu / zi - minn < 0){minn = mu / zi;for (int i = 1; i <= m; i++){ans[i] = index[i];}}return;}for (int i = cur + 1; i <= n; i++){
///
// g[dep][dep + 1] = g[dep + 1][dep] = edgeWeight[cur][i];
// index[dep] = cur;
// index[dep + 1] = i;dfs(i, dep + 1);}
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALwhile (~scanf("%d%d", &n, &m)){if (!n && !m)break;for (int i = 1; i <= n; i++){scanf("%d", &nodeWeight[i]);}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){scanf("%d", &edgeWeight[i][j]);}}minn = inf;for (int i = 1; i <= n; i++){dfs(i, 1);}//cout << "minn" << minn << endl;for (int i = 1; i <= m - 1; i++){printf("%d ", ans[i]);}printf("%d\n", ans[m]);}return 0;
}
这篇关于hdu 2489 (dfs枚举 + prim)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
