1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<queue>  5   6 using namespace std;  7   8 bool flag[16],outp[16];  9 int n,m,node[16]; 10 int ma[16][16]; 11 double mi; 12  13 typedef struct heaptyp 14 { 15     int num,key; 16     friend bool operator < (heaptyp a,heaptyp b) 17     { 18         return a.num>b.num; 19     } 20 } heaptype; 21  22 void prim(int s,int tot) 23 { 24     int i,j,now,ans; 25     bool fla[16]; 26     priority_queue<heaptype>heap; 27     heaptype aaa; 28      29     memset(fla,0,sizeof(fla)); 30     fla[s]=true; 31     ans=0; 32     for (i=1;i<=n;i++)  33     if (flag[i]&&ma[s][i]) 34     { 35         heaptype temp; 36         temp.num=ma[s][i]; 37         temp.key=i; 38         heap.push(temp); 39         aaa=heap.top(); 40     } 41      42     for (j=1;j<m;j++) 43     { 44         heaptype h=heap.top(); 45         heap.pop(); 46         aaa=heap.top(); 47         while (fla[h.key]) 48         { 49             h=heap.top(); 50             heap.pop(); 51         } 52         now=h.key; 53         fla[now]=true; 54         ans+=h.num; 55         for (i=1;i<=n;i++) 56         if (flag[i]&&ma[now][i]) 57         if (!fla[i]) 58         { 59             heaptype temp; 60             temp.num=ma[now][i]; 61             temp.key=i; 62             heap.push(temp); 63             aaa=heap.top(); 64         } 65     } 66     double rat=(double)ans/tot; 67     if (mi-rat>0.0000001) 68     { 69         mi=rat; 70         for (int i=1;i<=n;i++) outp[i]=fla[i]; 71     } 72 } 73  74 void dfs(int now,int last,int tot) 75 { 76      if (now==m) 77      { 78          int i; 79          for (i=1;i<=n;i++) 80          if (flag[i]) break; 81          prim(i,tot); 82      } 83      else  84      { 85          now++; 86          for (int i=last+1;i<=n-m+now;i++) 87          { 88              flag[i]=true; 89              dfs(now,i,tot+node[i]); 90              flag[i]=false; 91          } 92      } 93 } 94  95 int main() 96 { 97     scanf("%d%d",&n,&m); 98     while (!(n==0&&m==0)) 99     {100         for (int i=1;i<=n;i++) scanf("%d",&node[i]);101         for (int i=1;i<=n;i++)102         for (int j=1;j<=n;j++) scanf("%d",&ma[i][j]);103         104         mi=2147483647;105         memset(flag,0,sizeof(flag));106         for (int i=1;i<=n-m+1;i++)107         {108             flag[i]=true;109             dfs(1,i,node[i]);110             flag[i]=false;111         }112         113         int i;114         for (i=1;i<=n;i++) 115         if (outp[i]) 116         {117             printf("%d",i);118             break;119         }120         for (int j=i+1;j<=n;j++)121         if (outp[j]) printf(" %d",j);122         printf("\n");123         scanf("%d%d",&n,&m);124     }125     126     return 0;127 }