题意分析

我们需要在给定的完全图中找到一个由$m$个节点构成的生成树，使得该树的比率$\frac{\sum{边权重}}{\sum{节点权重}}$最小。比率越小，说明单位节点权重下的边权重越小，即树的总边权相对较小或节点总权相对较大。

解题思路

1：求Ratio。

2：枚举子图，类似枚举子图问题我们可以用dfs回溯完成。

C++代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 16
#define INF 1000000
using namespace std;
int n,m,node[N],edge[N][N],fin[N],d[N],use[N];
double ans;
double Prim()
{
	int s,pos,res,cnt=0;
	for(int i=0;i<m;i++) 
	   d[use[i]]=INF;
	s=use[0];
	for(int i=1;i<=m-1;i++)
	{
		res=INF;
		d[s]=-1;
		for(int j=0;j<m;j++)
		{
			if(s!=use[j]&&d[use[j]]>0)
			{
				d[use[j]]=min(d[use[j]],edge[s][use[j]]);
				if(d[use[j]]<res)
				{
					res=d[use[j]];
					pos=use[j];	
				}	
			}
		}
		s=pos;
		cnt+=res;	
	}
	res=0;
	for(int i=0;i<=m-1;i++)
		res+=node[use[i]];
	return 1.0*cnt/res;	
}
void dfs(int dep,int pos)
{
	if(dep>m||pos>n+1)//注意是n+1 
		return;
	if(dep==m)
	{
		double tem=Prim();
		if(tem<ans)
		{
			ans=tem;
			for(int i=0;i<m;i++)
			   fin[i]=use[i];
			return ;
		}
	}
	use[dep]=pos;//重建点 
	dfs(dep+1,pos+1);
	dfs(dep,pos+1);
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(!n&&!m)	
			break;
		for(int i=1;i<=n;i++)
		    scanf("%d",&node[i]);
		for(int i=1;i<=n;i++)
		    for(int j=1;j<=n;j++)
			scanf("%d",&edge[i][j]);
		ans=INF;
		dfs(0,1);//从0，1开始搜索 
		for(int i=0;i<m;i++)
		    printf("%d%s",fin[i],i==m-1?"\n":" ");	
	}	
//	while(1);
	return 0;
}