霸州住房和城乡建设厅网站,合肥仿站定制模板建站,网站开发主流方法,南宁网站建设lilkjhttps://vjudge.net/problem/HDU-2489 题意#xff1a;求一个完全图的最优比率生成树#xff0c;点的个数由题给出。最优比率生成树是边的权值之和与点的权值之和的比值最小的生成树。 思路#xff1a;一开始用dfs枚举搜索每一种情况#xff0c;t了#xff0c;枚举的情况太…https://vjudge.net/problem/HDU-2489 题意求一个完全图的最优比率生成树点的个数由题给出。最优比率生成树是边的权值之和与点的权值之和的比值最小的生成树。 思路一开始用dfs枚举搜索每一种情况t了枚举的情况太多。之后看了题解用的是状态压缩的方法枚举点的选择这样的情况要少得多。至于其他的细节倒是很好想由于比值最小所以我们要求的是一棵最小生成树再比上点的权值之和最后选择出最小的就行了。 1 #include stdio.h2 #include string.h3 #include map4 #include algorithm5 using namespace std;6 7 int n,m;8 9 int par[20];10 int a[20][20];11 int b[20];12 13 struct node14 {15 int x,y,d;16 } g[1000];17 18 void init(int k)19 {20 for (int i 0;i k;i)21 par[i] i;22 }23 24 int fin(int x)25 {26 if (x par[x]) return x;27 else return par[x] fin(par[x]);28 }29 30 void unit(int x,int y)31 {32 x fin(x);33 y fin(y);34 35 if (x ! y) par[x] y;36 }37 38 bool cmp(node aa,node bb)39 {40 return aa.d bb.d;41 }42 43 double solve(int k)44 {45 init(n);46 47 int p[20],cnt 0;48 int num 0;49 50 for (int i 0;i n;i)51 {52 if (k (1 i)) p[cnt] i;53 }54 55 for (int i 0;i cnt;i)56 {57 for (int j i 1;j cnt;j)58 {59 g[num].x p[i];60 g[num].y p[j];61 g[num].d a[p[i]][p[j]];62 num;63 }64 }65 66 int sum 0,sm 0;67 68 for (int i 0;i cnt;i)69 {70 int t p[i];71 sum b[t];72 }73 74 sort(g,gnum,cmp);75 76 for (int i 0;i num;i)77 {78 int x g[i].x,y g[i].y;79 80 //printf(%d %d88\n,x,y);81 82 if (fin(x) fin(y)) continue;83 84 unit(x,y);85 86 sm g[i].d;87 }88 89 return 1.0 * sm / sum;90 }91 92 int main()93 {94 while (scanf(%d%d,n,m) ! EOF)95 {96 double minn 10000000000;97 98 if (!m !n) break;99
100
101 for (int i 0;i n;i)
102 scanf(%d,b[i]);
103
104 for (int i 0;i n;i)
105 for (int j 0;j n;j)
106 scanf(%d,a[i][j]);
107
108 int ba (1 n) - 1;
109
110 for (int i 3;i ba;i)
111 {
112 int num 0;
113
114 for (int j 0;j n;j)
115 {
116 if (i (1 j)) num;
117 }
118
119 if (num m)
120 {
121 //0printf(00\n);
122 double tmp solve(i);
123
124 if (tmp minn)
125 {
126 minn tmp;
127 }
128 }
129 }
130
131 int mark;
132
133 for (int i 3;i ba;i)
134 {
135 int num 0;
136
137 for (int j 0;j n;j)
138 {
139 if (i (1 j)) num;
140 }
141
142 if (num m)
143 {
144 double tmp solve(i);
145
146 if (tmp minn)
147 {
148 mark i;
149 break;
150 }
151 }
152 }
153
154 int p[20];
155
156 int cnt 0;
157
158 for (int i 0;i n;i)
159 {
160 if (mark (1 i)) p[cnt] i;
161 }
162
163 for (int i 0;i cnt;i)
164 {
165 if (!i) printf(%d,p[i]1);
166 else printf( %d,p[i]1);
167 }
168
169 printf(\n);
170 }
171
172 return 0;
173 } 再附上一份t了的代码 1 #include stdio.h2 #include string.h3 #include algorithm4 #include map5 #include vector6 using namespace std;7 8 int n,m;9 int num 0;10 int par[20];11 int a[20];12 int b[20][20];13 bool v[20];14 int s[20];15 vectorint vv[10005];16 mapdouble,int mmp;17 18 double minn;19 20 struct node21 {22 int x,y,d;23 } g[500];24 25 bool cmp(node aa,node bb)26 {27 return aa.d bb.d;28 }29 30 void init(int k)31 {32 for (int i 0;i k;i)33 par[i] i;34 }35 36 int fin(int x)37 {38 if (x par[x]) return x;39 else return par[x] fin(par[x]);40 }41 42 void unit(int x,int y)43 {44 x fin(x);45 y fin(y);46 47 if (x ! y) par[x] y;48 }49 50 void solve(void)51 {52 int cnt 0;53 54 bool f 0;55 56 init(n);57 58 for (int i 0;i m;i)59 for (int j i 1;j m;j)60 {61 int x s[i],y s[j];62 if (b[x][y])63 {64 g[cnt].x x;65 g[cnt].y y;66 g[cnt].d b[x][y];67 cnt;68 }69 }70 71 int sum 0;72 73 for (int i 0;i m;i)74 {75 int t s[i];76 77 sum a[t];78 }79 80 sort(g,gcnt,cmp);81 82 int sm 0;83 84 for (int i 0;i cnt;i)85 {86 int x g[i].x,y g[i].y;87 88 if (fin(x) fin(y)) continue;89 90 sm g[i].d;91 92 unit(x,y);93 }94 95 int rt fin(s[0]);96 97 for (int i 0;i m;i)98 {99 if (fin(s[i]) ! fin(rt)) f 1;
100 }
101
102 double now 1.0 * sm / sum;
103
104 if (!f now minn)
105 {
106 if (!mmp[now])
107 {
108 mmp[now] num;
109 minn now;
110
111 for (int i 0;i m;i)
112 vv[num].push_back(s[i]);
113
114 num;
115 }
116
117 }
118 }
119
120 void dfs(int i,int p)
121 {
122 if (m n p m - 1)
123 {
124 s[p] i;
125 solve();
126 return;
127 }
128 else if (m n p m)
129 {
130 solve();
131 return;
132 }
133
134 s[p] i;
135
136 for (int j 0;j n;j)
137 {
138 if (!v[j])
139 {
140 v[j] 1;
141 dfs(j,p1);
142 v[j] 0;
143 }
144 }
145 }
146
147
148 int main()
149 {
150 while (scanf(%d%d,n,m) ! EOF)
151 {
152 if (m 0 n 0) break;
153
154 num 0;
155
156 minn 1000000000;
157
158 memset(v,0,sizeof(v));
159 memset(s,0,sizeof(s));
160 memset(a,0,sizeof(a));
161 memset(b,0,sizeof(b));
162 memset(g,0,sizeof(g));
163 memset(vv,0,sizeof(vv));
164
165 for (int i 0;i n;i)
166 scanf(%d,a[i]);
167
168
169 for (int i 0;i n;i)
170 for (int j 0;j n;j)
171 scanf(%d,b[i][j]);
172
173 for (int i 0;i n;i)
174 {
175 v[i] 1;
176 dfs(i,0);
177 v[i] 0;
178 }
179
180 int k mmp[minn];
181
182 sort(vv[k].begin(),vv[k].end());
183
184 for (int i 0;i vv[k].size();i)
185 {
186 if (!i) printf(%d,vv[k][i] 1);
187 else printf( %d,vv[k][i] 1);
188 }
189
190 printf(\n);
191 }
192
193 return 0;
194 } 转载于:https://www.cnblogs.com/kickit/p/7150817.html
