uva 544(kruskal 变形)-白红宇

uva 544(kruskal 变形)

阅读量：6304 次

发布时间：2019-06-22

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

题意：在一张无向带权图中，求a-b的一条路经满足这条路径上的最小的边最大。

思路：仔细一看就能发现这不是最小瓶颈路的变形嘛，最小瓶颈路是让你求最大的边最小，这道题的意思就是反了一下，而且还是单组询问的。所以我们用kruskal先求最大生成树，然后第一次合并询问节点的边即为答案。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-02-05 17:03 5  * Filename     : uva_544.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 int n, m, parent[LEN], st, ed;35 map
                      
                        mp;36 struct edge{ int fr, to, val;}e[LEN*LEN];37 38 void init(){39 mp.clear();40 for(int i=0; i
                       
                         b.val;}44 45 int kruskal()46 {47 sort(e, e+m, cmp);48 for(int i=0; i

View Code

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

你可能感兴趣的文章