思路：
直接状态压缩暴力枚举
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define Maxn 30
#define inf 10000000
using namespace std;
int ans,n,m;
int c,d;
int map[Maxn][Maxn];
int lis[Maxn],node[Maxn];
int val[<<],sum[<<];
int main()
{
int i,j;
while(scanf("%d%d",&n,&m),n||m){
memset(val,,sizeof(val));
memset(sum,,sizeof(sum));
c=,d=;
for(i=;i<=n;i++)
scanf("%d",&node[i]);
memset(map,,sizeof(map));
for(i=;i<=n;i++){
for(j=;j<=n;j++){
scanf("%d",&map[i][j]);
}
}
int N=<<n;
N-=;
int cnt=;
val[]=;
for(i=;i<=n;i++)
val[<<i]=;
for(i=;i<=N;i++){
cnt=;
for(j=;j<n;j++){
if(i&(<<j)) lis[++cnt]=j+,sum[i]+=node[j+];
}
if(cnt>m) continue;
if(cnt==m)
{
int a=val[i],b=sum[i];
if(a*d<c*b){
ans=i;
c=a;
d=b;
}
}
int temp;
for(j=;j<n;j++){
if(((<<j)&i)==){
temp=inf;
for(int k=;k<=cnt;k++){
temp=min(temp,map[j+][lis[k]]);
}
val[i|(<<j)]=min(val[i]+temp,val[i|(<<j)]);
}
}
}
int num=;
for(j=;j<n;j++)
if((<<j)&ans){
printf("%d",j+);
if(num!=m)
printf(" ");
num++;
}
printf("\n");
}
return ;
}