题目大意：

给出一个图，要求在图中选取一些节点和边构成一个“边权和/点权和”最小的树。

思路：

用深搜从遍历所有m个点的选择方案，方案一旦确定，点权值也被确定。然后用最小生成树计算边权值。建立一个数组tree[]记录结果，将当前最小比值的选择方案存入tree[]中。

下面代码有一点需要注意，因为之前编写prim模板时将变量n定义为节点数量，而本题题干中定义m才为需要计算的节点的数量，n则为总节点数量。所以此题中m与n的定义与题干中相反。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
#define maximum 2147483647
#define datasize 15
int key[datasize+1],v[datasize+1],map[datasize+1][datasize+1],heap_size_a,length_a,sum,n;
//以上是prim使用到的变量。 
int parent(int i)
{
	return i/2;
}
int left(int i)
{
	return 2*i;
}
int right(int i)
{
	return 2*i+1;
}
void min_heapify(int a[],int i)
{
	int l=left(i),r=right(i),least;
	if(l<=heap_size_a&&a[l]<a[i])
		least=l;
	else
		least=i;
	if(r<=heap_size_a&&a[r]<a[least])
		least=r;
	if(least!=i)
	{
		swap(a[i],a[least]);
		swap(v[i],v[least]);
		min_heapify(a,least);
	}
}
void build_min_heap(int a[])
{
	heap_size_a=length_a;
	for(int i=length_a/2;i>=1;i--)
		min_heapify(a,i);
}
//以上为堆基本操作，以下为优先队列基本操作  
int heap_extract_min(int a[])
{
	int min=v[1];
	sum+=a[1];
	a[1]=a[heap_size_a];
	v[1]=v[heap_size_a];
	heap_size_a--;
	min_heapify(a,1);
	return min;
}
void heap_decrease_key(int a[],int i,int key)
//key不能大于元素i的值 
{
	a[i]=key;
	while(i>1&&a[parent(i)]>a[i])
	{
		swap(a[i],a[parent(i)]);
		swap(v[i],v[parent(i)]);
		i=parent(i);
	}
}
void prim(int r)
{
	for(int i=1;i<=datasize;i++)
	{
		key[i]=maximum;
		v[i]=i;
	}
	key[r]=0;
	length_a=n;
	build_min_heap(key);
	while(heap_size_a>=1)
	{
		int u=heap_extract_min(key);
		for(int i=1;i<=heap_size_a;i++)
			if(map[u][v[i]]<key[i])
				heap_decrease_key(key,i,map[u][v[i]]);
	}
}
int original[datasize+1][datasize+1],val[datasize+1],m;
//original[][]存储由输入给出的边权矩阵。
//val[]存储点权值。
//m表示图全部点的个数。 
void intput()
//输入 
{
	for(int i=1;i<=m;i++)
		scanf("%d",&val[i]);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&original[i][j]);
}
int tree[datasize+1];
//存储答案 
double ratio;
//ratio当前最小比值。 
bool dfs(int start,int order,int total)
//从start开始遍历，第order个节点，点权值和为total。 
{
	if(order==n+1)
	{
		sum=0;
		//初始化边权和。 
		prim(1);
		//调用prim()计算边权和。 
		if(ratio>double(sum)/double(total))
		//若当前方案中的比值小于最小比值。 
		{
			ratio=double(sum)/double(total);
			return true;
		}
		return false;
	}
	bool check=false;
	//check用于判断当前以order个点为基础延伸出的方案中是否有比值小于ratio的方案。 
	for(int i=start,res;i<=m-(n-order);i++)
	{
		map[order][0]=i;
		for(int j=1;j<=order;j++)
		//利用original[][]构建order个节点的新邻接矩阵map[][]。 
			map[order][j]=map[j][order]=original[i][map[j][0]];
		if(dfs(i+1,order+1,total+val[i]))
		//若以当前order个节点为基础延伸出的方案中有比值小于ratio的方案。 
		{
			tree[order]=i;
			//用tree[]记录下更优方案中的第order个节点i。 
			check=true;
		}
	}
	return check;
}
int main()
{
	while(scanf("%d%d",&m,&n)&&(m||n))
	{
		intput();
		ratio=100;
		//初始化ratio为一个不可能达到的最大值。（n*100）/(n*1-1)趋近于100。 
		dfs(1,1,0);
		for(int i=1;i<=n;i++)
		//输出结果。 
			if(i-n)
				printf("%d ",tree[i]);
			else
				printf("%d\n",tree[i]);
	}
}