https://vjudge.net/problem/HDU-4081
题意：
秦始皇想要修长城，修成生成树的样子，这是一个大师出现了，他说他可以不耗费人力修出一条路来。他们的目的很不一样，神特么有分歧，最后他们达成了一个协议，假设一个城市的人口为a。那么最后不耗费人力修的那条路所相连的两个城市的人口之和A与修路花费的人力B之比 A/B最大，并且输出最大值。
思路：
枚举去掉每一条边。
首先求出最小生成树，对于最小生成树中的每一条边，如果这条边不花费人力，那么直接计算A和B就可以了。
那么问题是如果选择的边不在最小生成树中的话，应该怎么办。为了形成生成树，肯定要将最小生成树生成树中的边去掉，又为了保持边的权值之和是最小的，所以自然想到了次小生成树，用到了maxn[u][v]那个数组，所以就将maxn[u][v]减去进行比较就行了。maxn[u][v]的求法请见次小生成树学习的博文。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 struct node 10 { 11 int x,y; 12 double len; 13 } a[1000005]; 14 15 struct com 16 { 17 int id; 18 double dis; 19 }; 20 21 int h[1005],z[1005],p[1005]; 22 int par[1005]; 23 bool v[1000005]; 24 double ma[1005][1005]; 25 bool vis[1005]; 26 vector no[1005]; 27 28 bool cmp(node aa,node bb) 29 { 30 if (aa.len == bb.len) 31 { 32 double t1 = p[aa.x] + p[aa.y]; 33 double t2 = p[bb.x] + p[bb.y]; 34 35 return t2 < t1; 36 } 37 38 return aa.len < bb.len; 39 } 40 41 void init(int n) 42 { 43 for (int i = 0;i < n;i++) 44 par[i] = i; 45 } 46 47 int fin(int x) 48 { 49 if (x == par[x]) return x; 50 else return par[x] = fin(par[x]); 51 } 52 53 void unit(int x,int y) 54 { 55 x = fin(x); 56 y = fin(y); 57 58 if (x != y) par[x] = y; 59 } 60 61 double cal(int i,int j) 62 { 63 double dis1 = 1.0 * (h[i] - h[j]) * (h[i] - h[j]); 64 double dis2 = 1.0 * (z[i] - z[j]) * (z[i] - z[j]); 65 66 return sqrt(dis1 + dis2); 67 } 68 69 void adde(int x,int y,double dis) 70 { 71 node t; 72 73 t.x = x; 74 t.y = y; 75 t.len = dis; 76 77 no[x].push_back(t); 78 } 79 80 void bfs(int k) 81 { 82 memset(vis,0,sizeof(vis)); 83 84 com now,nex; 85 86 queue qq; 87 88 while (!qq.empty()) qq.pop(); 89 90 now.id = k;now.dis = 0; 91 vis[now.id] = 1; 92 93 qq.push(now); 94 95 while (!qq.empty()) 96 { 97 com tc = qq.front();qq.pop(); 98 99 int tx = tc.id;100 double maxn = tc.dis;101 102 for (int i = 0;i < no[tx].size();i++)103 {104 node tmp = no[tx][i];105 int ty = tmp.y;106 double tmaxn = tmp.len;107 108 if (!vis[ty])109 {110 vis[ty] = 1;111 nex.id = ty;112 nex.dis = tmaxn;113 114 if (maxn > tmaxn) nex.dis = maxn;115 116 ma[k][ty] = nex.dis;117 118 qq.push(nex);119 }120 }121 }122 }123 124 int main()125 {126 int t;127 128 scanf("%d",&t);129 130 while (t--)131 {132 int n;133 134 scanf("%d",&n);135 136 init(n);137 memset(a,0,sizeof(a));138 memset(v,0,sizeof(v));139 memset(no,0,sizeof(no));140 141 for (int i = 0;i < n;i++)142 {143 scanf("%d%d%d",&h[i],&z[i],&p[i]);144 }145 146 int cnt = 0;147 148 for (int i = 0;i < n;i++)149 for (int j = i + 1;j < n;j++)150 {151 a[cnt].x = i;a[cnt].y = j;152 a[cnt].len = cal(i,j);153 cnt++;154 }155 156 double es = 0;157 158 sort(a,a+cnt,cmp);159 160 for (int i = 0;i < cnt;i++)161 {162 int x = a[i].x,y = a[i].y;163 164 if (fin(x) == fin(y)) continue;165 166 unit(x,y);167 168 v[i] = 1;169 170 adde(x,y,a[i].len);171 adde(y,x,a[i].len);172 173 es += a[i].len;174 }175 176 double maxn = 0;177 178 for (int i = 1;i <= n;i++)179 {180 bfs(i);181 }182 183 for (int i = 0;i < cnt;i++)184 {185 if (v[i])186 {187 double ns = 0;188 int x = a[i].x,y = a[i].y;189 190 ns += p[x];ns += p[y];191 192 es -= a[i].len;193 194 if (ns / es > maxn) maxn = ns / es;195 196 es += a[i].len;197 }198 else199 {200 double ns = 0;201 int x = a[i].x,y = a[i].y;202 203 ns += p[x];ns += p[y];204 205 es -= ma[x][y];206 207 if (ns / es > maxn) maxn = ns / es;208 209 es += ma[x][y];210 }211 }212 213 printf("%.2f\n",maxn);214 }215 216 return 0;217 }