杭電oj HDOJ 2489 Minimal Ratio Tree(DFS最小生成樹)

杭州電oj HDOJ 2489 Minimal Ratio Tree
タイトルのソース:http://acm.hdu.edu.cn/showproblem.php?pid=2489
Problem Description
For a tree,which nodes and edges are all weightted,the ratio of it is callted according to the following equation. Gvent a compreet grath of n nodes and edges weight,your task fired.with m nodes and whose ratio is the smalest among all the trees of m nodes in the grapph.
Input
Input contains multiple test cases.The first line of each test case contains two integers n(2<=n==15)and m(2<=m==n)、which stands for the number of nodes in the graphh and the number of nodes in in the minimation ratio.Two zros end the input.The next line contains n n numbers which stand for the weight of each.The windowline.×n connectivity matrix with each element shows the weight of the edge connecting one node with another.Of course,the diagonal will be all 0,since there isのedge connecting a node with itself.
All the weights of both nodes and edges(except for the ons on the diagonal of the matirix)ar integers and in the range of[1,100]
The figure below illustration the first test case in sample input.Node 1 and Node 3 form the minimal ratie.
Ouut
For each test case output one line contains a sequence of the m nodes which construts the minimal ratio tree.Nodes shound be arranged in ascending order.If there are several such sequences,pick the one which the smbers smbersif there’s a tie、look at the second smalest node number、etc.Please note that the nodes are numbend from 1.
タイトルの大意
一本の木の比率は「幾つかの辺の重みの和」と定義され、「これらの辺の間の点の重みの和」と除算される.nを与えます× n\times n×nの図は、生成ツリーを求めることにより、その点にm個があり、その比率が最小となる.この木の結点番号は大きいから小さいまで出力します.
問題を解く構想
nの範囲は2から15までですので、m個の結点を挙げた木は全部でもタイムアウトしません.したがって、DFS枚を利用して、すべての場合を挙げて、Primアルゴリズムを用いて最小生成ツリーを求め、その最小比率ツリーの結点を保存し、最後に出力します.
C++コード

#include 
#include 
#include 
#include 
#define inf 0x3f3f3f
using namespace std;

int graph[16][16];	
int nodeWeight[16];				//       
int dist[16];					//            
bool mark[16];
int n, m;
vector<int> v, min_v;
vector<vector<int>> V;
void init(vector<int>);			//          
void Prim();					// Prim  ，        
double radio(vector<int>);		//     
//       
//                 
//                 
void DFS(int, int);

int main()
{
	int i, j;
	double min_radio, temp;
	while (cin >> n >> m) {
		if (!n) {
			break;
		}
		for (i = 1; i <= n; i++) {
			cin >> nodeWeight[i];
		}
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= n; j++) {
				cin >> graph[i][j];
			}
		}
		//                       
		DFS(1, 0);
		//               
		for (i = 0; i < V.size(); i++) {
			init(V[i]);
			Prim();
			for (j = 1; j <= n; j++) {
				temp = radio(V[i]);
				if (!i) {
					min_radio = temp;
					min_v = V[i];
				}
				else {
					if (temp < min_radio) {
						min_radio = temp;
						min_v = V[i];
					}
				}
			}
		}
		for (i = 0; i < m; i++) {
			if (i) {
				cout << " ";
			}
			cout << min_v[i];
		}
		cout << endl;
		V.clear();
	}
}

void init(vector<int> v) {
	//           
	memset(dist, 0, sizeof(dist));
	//               
	memset(mark, 1, sizeof(mark));
	//              ，             
	for (int i = 1; i < m; i++) {
		dist[v[i]] = graph[v[0]][v[i]];
		mark[v[i]] = false;
	}
}

void Prim() {
	int i, j, temp, pos;
	for (i = 1; i < m; i++) {
		temp = inf;
		//               
		for (j = 1; j <= n; j++) {
			if (!mark[j] && dist[j] < temp) {
				temp = dist[j];
				pos = j;
			}
		}
		mark[pos] = true;
		for (j = 1; j <= n; j++) {
			if (!mark[j]) {
				//       
				dist[j] = min(dist[j], graph[pos][j]);
			}
		}
	}
}

double radio(vector<int> v) {
	int i,	numer = 0, denom = 0;
	for (i = 0; i < m; i++) {
		numer += dist[v[i]];
		denom += nodeWeight[v[i]];
	}
	return double(numer) / denom;
}

void DFS(int num, int count)
{
	if (num > n) {
		//                     
		if (count == m) {
			for (int i = 1; i <= n; i++) {
				if (mark[i]) {
					v.push_back(i);
				}
			}
			V.push_back(v);
			v.clear();
		}
	}
	else {
		mark[num] = true;
		DFS(num + 1, count + 1);
		mark[num] = false;
		DFS(num + 1, count);
	}
}

問題を発見したら、指摘と訂正を歓迎します.ありがとうございます.