uvaLive5713 次小生成树-白红宇

uvaLive5713 次小生成树

阅读量：4551 次

发布时间：2019-06-08

本文共 3015 字，大约阅读时间需要 10 分钟。

修建道路使得n个点任意两点之间都可以连通，每个点有都有一定的人口，现在可以免费修一条道路，

A是免费修的道路两端结点的人口之和， B的其它不是免费修道路的长度的总和

要求的是A/B的最短值。

B其实就是最小生成树删除一条边只有的权值之和B。只要我们知道生成树上任意两点之间的最长边，那么只要在这两点之间修一条边，

然后删除最长边，它还是一棵树。而已这时候的权值之和是B-maxCost[u][v]

那么答案就是min{p[u][v] / (B-maxCost[u][v])} , 枚举u，v的时间复杂度是O（n*n）。

至于得到maxCost[u][v] 只要在得到最小生成树之后，一遍dfs就可以求出

求解的方法是：当访问一个新节点时，计算所有已经访问过的结点到这个结点的最小权值

max[u][x] = maxCost[x][u] = max(maxCost[x][fa],edge(u,fa))

u是当前访问的结点，fa是u的父亲， x是所有已经访问过的结点。

（其实就是两个嵌套的循环，只不过是在树上循环罢了）

总的时间复杂度是n*n + e*loge 常数没有计算进去。

n*n和eloge 最大时都是1000多w， 3s的时间，足够了

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
               10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 using namespace std; 14 #pragma warning(disable:4996) 15 #pragma comment(linker, "/STACK:1024000000,1024000000") 16 typedef long long LL; 17 const int INF = 1<<30; 18 /* 19 20 */ 21 const int N = 1000 + 10; 22 struct Edge 23 { 24 int form, to, p; 25 double dist; 26 bool operator<(const Edge&rhs)const 27 { 28 return dist < rhs.dist; 29 } 30 }a[N*N]; 31 int x[N], y[N], p[N]; 32 int father[N]; 33 double maxCost[N][N]; 34 int p2[N][N]; 35 vector
                  
                    g[N]; 36 vector
                   
                     st; 37 int find(int x) 38 { 39 if (x == father[x]) 40 return x; 41 return father[x] = find(father[x]); 42 } 43 double kruskal(int n) 44 { 45 double sum = 0; 46 for (int i = 0; i < n; ++i) 47 { 48 int fx = find(a[i].form); 49 int fy = find(a[i].to); 50 if (fx != fy) 51 { 52 //记录生成树，用来等下dfs 53 g[a[i].form].push_back(a[i]); 54 swap(a[i].form, a[i].to); 55 g[a[i].form].push_back(a[i]); 56 sum += a[i].dist; 57 father[fx] = fy; 58 } 59 } 60 return sum; 61 } 62 63 /* 64 这个dfs其实就是给定一棵树，然后求任意两点之间的最大边权， 因为是任意两点， 那么时间复杂度无疑就是O(n*n) 65 */ 66 void dfs(int u, int fa, double dis) 67 { 68 if (fa!=-1) 69 for (int i = 0; i < st.size(); ++i) 70 { 71 int x = st[i]; 72 maxCost[x][u] = maxCost[u][x] = max(maxCost[x][fa], dis); 73 } 74 st.push_back(u); 75 for (int i = 0; i < g[u].size(); ++i) 76 { 77 int v = g[u][i].to; 78 if (v == fa) continue; 79 dfs(v, u, g[u][i].dist); 80 } 81 } 82 int main() 83 { 84 int t, n, cnt; 85 double B; 86 scanf("%d", &t); 87 while (t--) 88 { 89 scanf("%d", &n); 90 cnt = 0; 91 st.clear(); 92 for (int i = 0; i < n; ++i) 93 { 94 father[i] = i; 95 g[i].clear(); 96 scanf("%d%d%d", &x[i], &y[i], &p[i]); 97 } 98 for (int i = 0; i < n; ++i) 99 {100 for (int j = i + 1; j < n; ++j)101 {102 p2[i][j] = p2[j][i] = p[i] + p[j];103 //边集数组104 a[cnt].form = i;105 a[cnt].to = j;106 a[cnt].p = p[i] + p[j];107 a[cnt++].dist = sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));108 }109 }110 sort(a, a + cnt);111 B = kruskal(cnt);112 dfs(0, -1, 0);113 double ans = 0;114 115 //枚举在哪两个之间建免费的道路116 for (int i = 0; i < n; ++i)117 for (int j = i + 1; j < n; ++j)118 ans = max(ans, p2[i][j] / (B - maxCost[i][j]));119 printf("%.2lf\n", ans);120 }121 return 0;122 }