题目大意：
给出一个图，要求在图中选取一些节点和边构成一个“边权和/点权和”最小的树。
思路：
用深搜从遍历所有m个点的选择方案，方案一旦确定，点权值也被确定。然后用最小生成树计算边权值。建立一个数组tree[]记录结果，将当前最小比值的选择方案存入tree[]中。
下面代码有一点需要注意，因为之前编写prim模板时将变量n定义为节点数量，而本题题干中定义m才为需要计算的节点的数量，n则为总节点数量。所以此题中m与n的定义与题干中相反。
代码：
#include
#include
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]=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=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;jdouble(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]);
}
}