首页 > 代码库 > hdu 2489 Minimal Ratio Tree(dfs枚举 + 最小生成树)~~~
hdu 2489 Minimal Ratio Tree(dfs枚举 + 最小生成树)~~~
题目:
链接:点击打开链接
题意:
输入n个点,要求选m个点满足连接m个点的m-1条边权值和sum与点的权值和ans使得sum/ans最小,并输出所选的m个点,如果有多种情况就选第一个点最小的,如果第一个点也相同就选第二个点最小的........
思路:
求一个图中的一颗子树,使得Sum(edge weight)/Sum(point weight)最小~
数据量小,暴力枚举~~~~~dfs暴力枚举C(M,N)种情况。
枚举出这M个点之后,Sum(point weight)固定,进行prim或者Kruskal算法使Sum(edge weight)最小。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define MAX 10000000 const int N = 20; int n,m; int w[N],ans[N],node[N]; int map[N][N],f[N][N]; int vis[N]; int low[N]; double res; int prim() { int pos,minn; int result = 0; memset(vis,0,sizeof(vis)); pos = 1; vis[pos] = 1; for(int i=1; i<=m; i++) { if(i != pos) low[i] = map[pos][i]; } for(int i=1; i<m; i++) { minn = MAX; for(int j=1; j<=m; j++) { if(!vis[j] && minn > low[j]) { minn = low[j]; pos = j; } } result += minn; vis[pos] = 1; for(int j=1; j<=m; j++) { if(!vis[j] && map[pos][j]<low[j]) low[j] = map[pos][j]; } } return result; } void dfs(int u,int cnt) { node[cnt] = u; if(cnt >= m) { for(int i=1; i<=m; i++) { for(int j=1; j<=m; j++) map[i][j] = f[node[i]][node[j]]; } double SumEdge = 1.0 * prim(); double SumPoint = 0; for(int i=1; i<=m; i++) { SumPoint += w[node[i]]; } double ratio1 = SumEdge/SumPoint; if(ratio1 - res < -1e-8) { res = ratio1; for(int i=1; i<=m; i++) ans[i] = node[i]; } return ; } for(int i=u+1; i<=n; i++) dfs(i,cnt+1); } int main() { //freopen("input.txt","r",stdin); while(scanf("%d%d",&n,&m) != EOF && (n || m)) { for(int i=1; i<=n; i++) scanf("%d",&w[i]); for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) scanf("%d",&f[i][j]); } res = MAX; for(int i=1; i<=n; i++) { dfs(i,1); } for(int i=1; i<m; i++) printf("%d ",ans[i]); printf("%d\n",ans[m]); } return 0; }
------------------------------------------------------------------
战斗,从不退缩;奋斗,永不停歇~~~~~~~~~~~~
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。