点的总数很小，直接枚举就好。
#include <stdio.h> #include <string.h> #define N 20 #define inf 1000000 int 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 ",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(" "); } return 0; }