题目大意：
给出一个图，要求在图中选取一些节点和边构成一个“边权和/点权和”最小的树。
思路：
用深搜从遍历所有m个点的选择方案，方案一旦确定，点权值也被确定。然后用最小生成树计算边权值。建立一个数组tree[]记录结果，将当前最小比值的选择方案存入tree[]中。
下面代码有一点需要注意，因为之前编写prim模板时将变量n定义为节点数量，而本题题干中定义m才为需要计算的节点的数量，n则为总节点数量。所以此题中m与n的定义与题干中相反。
代码：
1 | #include<iostream> |
2 | #include<stdio.h> |
3 | using namespace std; |
4 | #define maximum 2147483647 |
5 | #define datasize 15 |
6 | int key[datasize+1],v[datasize+1],map[datasize+1][datasize+1],heap_size_a,length_a,sum,n; |
7 | //以上是prim使用到的变量。 |
8 | int parent(int i) |
9 | { |
10 | return i/2; |
11 | } |
12 | int left(int i) |
13 | { |
14 | return 2*i; |
15 | } |
16 | int right(int i) |
17 | { |
18 | return 2*i+1; |
19 | } |
20 | void min_heapify(int a[],int i) |
21 | { |
22 | int l=left(i),r=right(i),least; |
23 | if(l<=heap_size_a&&a[l]<a[i]) least="l;" else="" if(r<="heap_size_a&&a[r]<a[least])" if(least!="i)" {="" swap(a[i],a[least]);="" swap(v[i],v[least]);="" min_heapify(a,least);="" }="" void="" build_min_heap(int="" a[])="" heap_size_a="length_a;" for(int="" i="length_a/2;i">=1;i--) |
24 | min_heapify(a,i); |
25 | } |
26 | //以上为堆基本操作，以下为优先队列基本操作 |
27 | int heap_extract_min(int a[]) |
28 | { |
29 | int min=v[1]; |
30 | sum+=a[1]; |
31 | a[1]=a[heap_size_a]; |
32 | v[1]=v[heap_size_a]; |
33 | heap_size_a--; |
34 | min_heapify(a,1); |
35 | return min; |
36 | } |
37 | void heap_decrease_key(int a[],int i,int key) |
38 | //key不能大于元素i的值 |
39 | { |
40 | a[i]=key; |
41 | while(i>1&&a[parent(i)]>a[i]) |
42 | { |
43 | swap(a[i],a[parent(i)]); |
44 | swap(v[i],v[parent(i)]); |
45 | i=parent(i); |
46 | } |
47 | } |
48 | void prim(int r) |
49 | { |
50 | for(int i=1;i<=datasize;i++) |
51 | { |
52 | key[i]=maximum; |
53 | v[i]=i; |
54 | } |
55 | key[r]=0; |
56 | length_a=n; |
57 | build_min_heap(key); |
58 | while(heap_size_a>=1) |
59 | { |
60 | int u=heap_extract_min(key); |
61 | for(int i=1;i<=heap_size_a;i++) |
62 | if(map[u][v[i]]<key[i]) heap_decrease_key(key,i,map[u][v[i]]);="" }="" int="" original[datasize+1][datasize+1],val[datasize+1],m;="" original[][]存储由输入给出的边权矩阵。="" val[]存储点权值。="" m表示图全部点的个数。="" void="" intput()="" 输入="" {="" for(int="" i="1;i<=m;i++)" scanf("%d",&val[i]);="" j="1;j<=m;j++)" scanf("%d",&original[i][j]);="" tree[datasize+1];="" 存储答案="" double="" ratio;="" ratio当前最小比值。="" bool="" dfs(int="" start,int="" order,int="" total)="" 从start开始遍历，第order个节点，点权值和为total。="" if(order="=n+1)" sum="0;" 初始化边权和。="" prim(1);="" 调用prim()计算边权和。="" if(ratio="">double(sum)/double(total)) |
63 | //若当前方案中的比值小于最小比值。 |
64 | { |
65 | ratio=double(sum)/double(total); |
66 | return true; |
67 | } |
68 | return false; |
69 | } |
70 | bool check=false; |
71 | //check用于判断当前以order个点为基础延伸出的方案中是否有比值小于ratio的方案。 |
72 | for(int i=start,res;i<=m-(n-order);i++) |
73 | { |
74 | map[order][0]=i; |
75 | for(int j=1;j<=order;j++) |
76 | //利用original[][]构建order个节点的新邻接矩阵map[][]。 |
77 | map[order][j]=map[j][order]=original[i][map[j][0]]; |
78 | if(dfs(i+1,order+1,total+val[i])) |
79 | //若以当前order个节点为基础延伸出的方案中有比值小于ratio的方案。 |
80 | { |
81 | tree[order]=i; |
82 | //用tree[]记录下更优方案中的第order个节点i。 |
83 | check=true; |
84 | } |
85 | } |
86 | return check; |
87 | } |
88 | int main() |
89 | { |
90 | while(scanf("%d%d",&m,&n)&&(m||n)) |
91 | { |
92 | intput(); |
93 | ratio=100; |
94 | //初始化ratio为一个不可能达到的最大值。（n*100）/(n*1-1)趋近于100。 |
95 | dfs(1,1,0); |
96 | for(int i=1;i<=n;i++) |
97 | //输出结果。 |
98 | if(i-n) |
99 | printf("%d ",tree[i]); |
100 | else |
101 | printf("%d\n",tree[i]); |
102 | } |
103 | } |
104 | </key[i])></a[i])></stdio.h></iostream> |
