uva 1494（MST+LCA）-白红宇

uva 1494（MST+LCA）

阅读量：6329 次

发布时间：2019-06-22

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

题意：有n个点告诉你每个点坐标和他上面的权值，任意两个点之间都有边权值是他们的距离，现在能免去花费一条边，定义a为这条边两个结点权值之和，b连通其余节点的最小花费，现在求a/b的最大值。

思路：先求最小生成树，然后枚举每条变，若加上边会成环则删除环上除去这条边的权值最大的边。

代码如下：

1 /**************************************************  2  * Author     : xiaohao Z  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/  4  * Last modified : 2014-02-08 13:40  5  * Filename     : uva_1494.cpp  6  * Description     :   7  * ************************************************/  8   9 #include 
      
        10 #include 
       
         11 #include 
        
          12 #include 
         
           13 #include 
          
            14 #include 
           
             15 #include 
            
              16 #include 
             
               17 #include 
              
                18 #include 
               
                 19 #include 
                 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair
                 
                   pii; 26 typedef pair
                  
                    puu; 27 typedef pair
                   
                     pid; 28 typedef pair
                    
                      pli; 29 typedef pair
                     
                       pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 1010; 34 const int LOGLEN = 22; 35 vector
                      
                        Map[LEN]; 36 int n, m, top, fa[LEN], dep[LEN], parent[LOGLEN][LEN], tag[LEN*LEN]; 37 double rd[LOGLEN][LEN]; 38 struct V{ double x, y, val;}; 39 struct E{ 40 int u, v; 41 double val; 42 }; 43 E edge[LEN*LEN]; 44 V vv[LEN]; 45 46 double dis(int a, int b){ 47 return sqrt((vv[a].x-vv[b].x)*(vv[a].x-vv[b].x) + (vv[a].y-vv[b].y)*(vv[a].y-vv[b].y)); 48 } 49 bool cmp(E a, E b){ return a.val < b.val;} 50 //UFSet 51 void init(){ for(int i=0; i
                       
                         dep[v]) swap(u, v); 98 double ret = 0; 99 for(int i=0; i
                        
                         > i) & 1){101 ret = max(ret, rd[i][v]);102 v = parent[i][v];103 }104 if(u == v) return ret;105 for(int i=LOGLEN-1; i>=0; i--)106 if(parent[i][u] != parent[i][v]){107 ret = max(ret, rd[i][u]);108 ret = max(ret, rd[i][v]);109 u = parent[i][u];110 v = parent[i][v];111 }112 ret = max(ret, rd[0][u]);113 ret = max(ret, rd[0][v]);114 return ret;115 }116 117 int main()118 {119 // freopen("in.txt", "r", stdin);120 121 int T;122 scanf("%d", &T);123 while(T--){124 scanf("%d", &n);125 for(int i=0; i

View Code

转载于:https://www.cnblogs.com/shu-xiaohao/p/3540816.html

你可能感兴趣的文章