HDU 2489 Minimal Ratio Tree

Minimal Ratio Tree

Time Limit: 1000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 2489
64-bit integer IO format: %I64d Java class name: Maina

For a tree, which nodes and edges are all weighted, the ratio of it is calculated according to the following equation.

Given a complete graph of n nodes with all nodes and edges weighted, your task is to find a tree, which is a sub-graph of the original graph, with m nodes and whose ratio is the smallest among all the trees of m nodes in the graph.

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 graph and the number of nodes in the minimal ratio tree. Two zeros end the input. The next line contains n numbers which stand for the weight of each node. The following n lines contain a diagonally symmetrical n×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 no edge connecting a node with itself.

All the weights of both nodes and edges (except for the ones on the diagonal of the matrix) are integers and in the range of [1, 100].

The figure below illustrates the first test case in sample input. Node 1 and Node 3 form the minimal ratio tree.

Output

For each test case output one line contains a sequence of the m nodes which constructs the minimal ratio tree. Nodes should be arranged in ascending order. If there are several such sequences, pick the one which has the smallest node number; if there's a tie, look at the second smallest node number, etc. Please note that the nodes are numbered from 1 .

Sample Input

Sample Output

1 3
1 2

Source

2008 Asia Regional Beijing

解题：枚举点集，对点集求最小生成树

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 const int maxn = 20;
 5 int e[maxn][maxn],d[maxn],val[maxn],n,m;
 6 bool vis[maxn],us[maxn],ans[maxn];
 7 int prim(int s) {
 8     memset(d,0x3f,sizeof d);
 9     memset(us,false,sizeof us);
10     int sum = d[s] = 0;
11     while(true) {
12         int minV = INF,idx = -1;
13         for(int i = 0; i < n; ++i)
14             if(!us[i] && vis[i] && d[i] < minV) minV = d[idx = i];
15         if(minV == INF || idx == -1) break;
16         us[idx] = true;
17         sum += minV;
18         for(int i = 0; i < n; ++i) {
19             if(!us[i] && vis[i] && d[i] > e[idx][i])
20                 d[i] = e[idx][i];
21         }
22     }
23     return sum;
24 }
25 int wval,nval;
26 void dfs(int dep,int cnt,int nsum) {
27     if(cnt == m) {
28         int tmp = prim(dep - 1);
29         if(wval == INF || wval*nsum > tmp*nval) {
30             wval = tmp;
31             nval = nsum;
32             memcpy(ans,vis,sizeof vis);
33         }
34         return;
35     }
36     if(dep >= n) return;
37     vis[dep] = true;
38     dfs(dep+1,cnt+1,nsum+val[dep]);
39     vis[dep] = false;
40     dfs(dep+1,cnt,nsum);
41 }
42 int main() {
43     while(scanf("%d %d",&n,&m),n||m) {
44         for(int i = 0; i < n; ++i)
45             scanf("%d",&val[i]);
46         for(int i = 0; i < n; ++i)
47             for(int j = 0; j < n; ++j)
48                 scanf("%d",e[i]+j);
49         memset(vis,false,sizeof vis);
50         wval = INF;
51         dfs(0,0,0);
52         bool flag = false;
53         for(int i = 0; i < n; ++i)
54             if(ans[i]) {
55                 if(flag) putchar(' ');
56                 flag = true;
57                 printf("%d",i+1);
58             }
59         putchar('
');
60     }
61     return 0;
62 }
63 
64 /*
65 3 2
66 30 20 10
67 0 6 2
68 6 0 3
69 2 3 0
70 
71 2 2
72 1 1
73 0 2
74 2 0
75 
76 0 0
77 */

View Code