Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2180 Accepted Submission(s): 630
Problem Description
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
3 2
30 20 10
0 6 2
6 0 3
2 3 0
2 2
1 1
0 2
2 0
0 0
Sample Output
1 3
1 2
Source
这道题是2008年北京现场比赛的一道题,题意大致意思是给定n个节点的一个图,要你从中选出这小边的权值和除以节点权值和的最小的一个树
于是很好理解的为最小生成树,采用普利姆最小生成树....注意精度的问题,这里我wa了n次
哎,喵了个咪
代码:
1 #include<string.h>
2 #include<stdlib.h>
3 #include<stdio.h>
4 #include<math.h>
5 #define max 0x3f3f3f3f
6 #define maxn 17
7 int node_weight[maxn];
8 int edge_weight[maxn][maxn];
9 int depath[maxn]; //以这些点形成一颗最小生成树
10 int m , n ;
11 double res;
12 int stu[maxn];
13 int sub_map[maxn][maxn];
14 void Prime()
15 {
16 int vis[maxn]={0};
17 int lowc[maxn];
18 int i,j,k,minc;
19 double ans=0;
20 for(i=1;i<=m;i++) //从n中挑出m个点形成一个子图
21 {
22 for(j=1;j<=m;j++)
23 {
24 if(edge_weight[depath[i]][depath[j]]==0)
25 sub_map[i][j]=max;
26 else
27 sub_map[i][j]=edge_weight[depath[i]][depath[j]];
28 }
29 }
30 vis[1]=1;
31 for(i=1;i<=m;i++)
32 {
33 lowc[i]=sub_map[1][i];
34 }
35 for(i=2;i<=m;i++)
36 {
37 minc=max;
38 k=0;
39 for(j=2;j<=m;j++)
40 {
41 if(vis[j]==0&&minc>lowc[j])
42 {
43 minc=lowc[j];
44 k=j;
45 }
46 }
47 if(minc==max) return ; //表示没有联通
48 ans+=minc;
49 vis[k]=1;
50 for(j=1 ; j<=m;j++)
51 {
52 if(vis[j]==0&&lowc[j]>sub_map[k][j])
53 lowc[j]=sub_map[k][j];
54 }
55 }
56 int sum=0;
57 for(i=1;i<=m;i++) //统计点权值的和
58 sum+=node_weight[depath[i]];
59 ans/=sum;
60 if(res+0.00000001>=ans)
61 {
62 if((res>=ans&&res<=ans+0.000001)||(res<=ans&&res+0.000001>=ans+0.000001))
63 {
64 for(i=1;i<=m;i++)
65 {
66 if(stu[i]<depath[i]) return;
67 }
68 }
69 res=ans;
70 memcpy(stu,depath,sizeof(depath));
71 }
72 }
73 void C_n_m(int st ,int count)
74 {
75 if(count==m)
76 {
77 Prime();
78 return ;
79 }
80 for(int i=st ;i<=n;i++ )
81 {
82 depath[count+1]=i;
83 C_n_m(i+1,count+1);
84 }
85 }
86 int main()
87 {
88 int i,j;
89 while(scanf("%d%d",&n,&m),m+n)
90 {
91 for(i=1;i<=n;i++)
92 scanf("%d",node_weight+i); //记录节点权值
93 for(i=1;i<=n;i++) //记录边权值
94 for(j=1;j<=n;j++)
95 scanf("%d",&edge_weight[i][j]);
96 // C(n,m)
97 res=max;
98 C_n_m(1,0);
99 for(i=1;i<=m;i++)
100 {
101 printf("%d",stu[i]);
102 if(i!=m)printf(" ");
103 }
104 putchar(10);
105 }
106 return 0;
107 }