哎 直接枚举所有m个点 求最小生成树
按题意来就行了。。
另外还要加一个剪枝
在存点的编号 用点的编号的地方wa了好久好久。。
#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll __int64 using namespace std; int ans[20],d[20],vis[20],s[20],w[20],e[20][20],n,m; double rat; void prim() { int i,j,t,minweight,p,tmp,sum; memset(vis,0,sizeof vis); minweight=0; p=s[1];vis[p]=1;d[p]=0; for(i=1;i<=m;i++) if(s[i]!=p) d[s[i]]=e[p][s[i]]; for(i=1;i d[t]) { tmp=d[t]; p=t; } } vis[p]=1; minweight+=d[p]; for(j=1;j<=m;j++) { t=s[j]; if(!vis[t]&&d[t]>e[t][p]) d[t]=e[t][p]; } } //更新最小minweight/sum sum=0; for(i=1;i<=m;i++) sum+=w[s[i]]; double tt=minweight*1.0/sum; if(tt