PKU 3925 Minimal Ratio Tree

問題

全ての辺と頂点に重みのついた、頂点数nの完全グラフが与えられる。
このグラフの部分木で頂点数がmのもののうちで、以下の値が最小になるようなものの頂点を小さい順に出力せよ。

Σ(部分木に含まれる頂点の重み)/Σ(部分木に含まれる頂点の重み)

複数ある場合は辞書順で最初に来るものを出力せよ。

制約条件

n≦15

方針

部分木の頂点の選び方は2^15通りしかないので全通り試せる。
頂点を決めたとき、その頂点からなるような部分木の「頂点の重みの和」の最小値はビットDPで計算できる。

ソースコード

int n,m, node[15],e[15][15];
int sum[1<<15], dp[1<<15];

int main()
{
	while(scanf("%d%d",&n,&m),n){
		rep(i,n)scanf("%d",node+i);
		rep(i,n)rep(j,n)scanf("%d",e[i]+j);
		
		rep(i,1<<n){
			dp[i]=inf;
			sum[i]=0;
			rep(j,n)if(i&1<<j)sum[i]+=node[j];
		}
		rep(i,n)dp[1<<i]=0;
		
		rep(i,1<<n)rep(j,n)if(i&1<<j)rep(k,n)if(!(i&1<<k))
			dp[i|1<<k]=min(dp[i|1<<k],dp[i]+e[j][k]);
		
		double mn=INF,tmp; int mni;
		for(int i=1;i<1<<n;i++){
			int bit=0;
			for(int j=i;j;j&=j-1)bit++;
			if(bit!=m)continue;
			
			tmp=dp[i]*1.0/sum[i];
			if(mn>tmp)mn=tmp, mni=i;
		}
		for(int i=0,j=0;i<n;i++)if(mni&1<<i)
			printf("%d%c",i+1,++j==m?'\n':' ');
	}
	return 0;
}