题意：在n个结点的完全图中，每条边和每个点都有一个权值。
定义：
从中选出m个结点组成一个连通图，顺序输出构成最小的ratio时所选取的m个点。
思路：边权之和最小，想到prim，同时n最大是15，直接暴力。先dfs出m个顶点，然后求出对应的ratio，找出最小的radio，输出结果就行了。
计算了一下15以内组合数的最大值是6000+，此时m为7或8，算上prim的O（n^2），时间是够的。一发AC！
#include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<set> #include<algorithm> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int N=18; int n,m,g[N][N],node[N]; int arr[N]; double ans; bool vis[N]; int Prim(){ //lowcost[i]记录结果集到结点i的最短距离，mst[i]记录结果集中到i最短距离的端点 int minn=inf,id=0,lowcost[N],mst[N]; int res=0; for(int i=0;i<n;++i){ if(vis[i]){ id=i; break; } } for(int i=0;i<n;++i){ if(vis[i]){ lowcost[i]=g[id][i]; mst[i]=id; } } for(int i=1;i<m;++i){ minn=inf; for(int i=0;i<n;++i){ if(vis[i]&&lowcost[i]&&lowcost[i]<minn){ minn=lowcost[i]; id=i; } } res+=minn; lowcost[id]=0; for(int i=0;i<n;++i){ if(vis[i]&&lowcost[i]&&g[id][i]<lowcost[i]){ lowcost[i]=g[id][i]; mst[i]=id; } } } return res; } void dfs(int k,int num){//k是当前下标，num是已标记点数 //printf("dfs:k=%d num=%d\n",k,num); if(num==m){ int we=Prim(); int wn=0; for(int i=0;i<n;++i){ if(vis[i]){ wn+=node[i]; } } double res=(double)we/wn; if(res<ans){ ans=res; for(int i=0,j=0;i<n;++i){ if(vis[i]){ arr[j++]=i;//数组arr记录选取的结点 } } } }else{ if(k==n)return;//搜索终点 if((n-k)<(m-num))return;//剪枝，减少递归层数 vis[k]=1; dfs(k+1,num+1); vis[k]=0; dfs(k+1,num); } } int main(){ while(~scanf("%d%d",&n,&m),m||n){ for(int i=0;i<n;++i){ scanf("%d",&node[i]); } for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ scanf("%d",&g[i][j]); } } memset(vis,0,sizeof(vis)); ans=99999999.0; dfs(0,0); for(int i=0;i<m-1;++i){ printf("%d ",arr[i]+1);//题目下标从1开始 } printf("%d\n",arr[m-1]+1); } }
