HDU-4081 (次小生成树 + kruskal)

题目大意：有n个城市，每个城市有人口数。给出城市的坐标和人口数。要建最小生成树，但可以选择一条魔法路径，不用花费成本。

魔法路径能够对A人口有利，A是这条魔法路径两端城市的人口总和，生成树的花费是B，求出最大的 A / B。

思路：本题没有直接要求求次小生成树，但需要用到次小生成树中的max数组。先求得最下生成树，再依次遍历每条边，

减去当前路径中的最大边，计算A / B，记录最大值。可以先把每个端点的人口数保存在边上。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<string>
  6 #include<cmath>
  7 #include<vector>
  8 
  9 using namespace std;
 10 typedef long long ll;
 11 const int maxn = 2e3 + 5;
 12 const int maxm = 2e6 + 5;
 13 
 14 int n, tot;
 15 
 16 struct Node{
 17     double x, y, p;
 18 }node[maxm];
 19 
 20 struct Edge
 21 {
 22     int x, y;
 23     double p, len;
 24 }edge[maxm];
 25 
 26 int f[maxn];
 27 int vis[maxm];
 28 double maxd[maxn][maxn];
 29 
 30 int head[maxm], End[maxm];
 31 struct data
 32 {
 33     int u, next;
 34 }G[maxn];
 35 
 36 double getlen(double x1, double y1, double x2, double y2){
 37     return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
 38 }
 39 
 40 bool cmp(Edge a, Edge b){
 41     return a.len < b.len;
 42 }
 43 
 44 int get(int x){
 45     if(x == f[x]) return f[x];
 46     return f[x] = get(f[x]);
 47 }
 48 
 49 double kru(){
 50     for(int i = 0; i < n; i++) {
 51         G[i].u = i;
 52         G[i].next = -1;
 53         head[i] = End[i] = i;
 54         f[i] = i;
 55         vis[i] = 0;
 56     }
 57     int cnt = 0;
 58     double ans = 0;
 59     for(int i = 0; i < tot; i++){
 60         int x = get(edge[i].x);
 61         int y = get(edge[i].y);
 62         if(x == y) continue;
 63         //---------------------次小生成树部分
 64         for(int j = head[x]; j != -1; j = G[j].next)
 65             for(int k = head[y]; k != -1; k = G[k].next)
 66                 maxd[G[j].u][G[k].u] = maxd[G[k].u][G[j].u] = edge[i].len;
 67         G[End[y]].next = head[x];
 68         head[x] = head[y];
 69         //---------------------
 70         f[y] = x;
 71         ans += edge[i].len;
 72         cnt++;
 73         vis[i] = 1;
 74         if(cnt == n - 1) break;
 75     }
 76     return ans;
 77 }
 78 
 79 int main()
 80 {
 81     int t;
 82     scanf("%d", &t);
 83     while(t--){
 84         scanf("%d", &n);
 85         for(int i = 0; i < n; i++){
 86             scanf("%lf %lf %lf", &node[i].x, &node[i].y, &node[i].p);
 87         }
 88         tot = 0;
 89         for(int i = 0; i < n; i++){
 90             for(int j = i + 1; j < n; j++){
 91                 double len = getlen(node[i].x, node[i].y, node[j].x, node[j].y);
 92                 edge[tot].x = i;
 93                 edge[tot].y = j;
 94                 edge[tot].len = len;
 95                 edge[tot++].p = node[i].p + node[j].p;
 96             }
 97         }
 98         sort(edge, edge + tot, cmp);
 99         double minlen = kru();
100         double ans = 0;
101         for(int i = 0; i < tot; i++){
102             ans = max(edge[i].p / (minlen - maxd[edge[i].x][edge[i].y]), ans);
103         }
104         printf("%.2f
", ans);
105     }
106     return 0;
107 }