首页 > 代码库 > hdu 2489 Minimal Ratio Tree 枚举+最小生成树
hdu 2489 Minimal Ratio Tree 枚举+最小生成树
点的总数很小,直接枚举就好。
#include <stdio.h>#include <string.h>#define N 20#define inf 1000000int mk[N],n,k,ans[N];double low[N],val[N];double map[N][N],MIN;double prim(){ int i,j; double sum=0; double tot=0; for(i=1;i<=n;i++) low[i]=inf; int u,v; for(i=1;i<=n;i++) if(mk[i]) { u=i; break; } sum+=val[u]; low[u]=-1; for(i=u+1;i<=n;i++) if(mk[i]) { low[i]=map[u][i]; sum+=val[i]; } for(i=1;i<=n-1;i++) { int minn=inf; for(j=1;j<=n;j++) { if(mk[j]&&low[j]!=-1&&low[j]<minn) { minn=low[j]; v=j; } } tot+=low[v]; low[v]=-1; for(j=1;j<=n;j++) if(low[j]!=-1&&mk[j]&&low[j]>map[v][j]) low[j]=map[v][j]; } return tot/sum;}void dfs(int tot,int now){ int i; if(tot>k) return ; if(now==n+1) { if(tot!=k) return ; double tmp=prim(); //printf("%lf\n",tmp); if(tmp<MIN) { MIN=tmp; for(i=1;i<=n;i++) ans[i]=mk[i]; } return ; } else { mk[now]=1; dfs(tot+1,now+1); mk[now]=0; dfs(tot,now+1); }}int main(){ while(1) { int i,j; scanf("%d%d",&n,&k); if(n+k==0) break; for(i=1;i<=n;i++) scanf("%lf",&val[i]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%lf",&map[i][j]); if(i==j) map[i][j]=inf; } MIN=inf; memset(ans,0,sizeof(ans)); dfs(0,1); for(i=1;i<=n;i++) if(ans[i]) { printf("%d",i); break; } i++; for(;i<=n;i++) if(ans[i]) printf(" %d",i); printf("\n"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。