【题意】

　　给出N个点，M条边，问这N个点形成的生成树的最大权值边-最小权值边的最小值

Input

The input consists of several test cases, separated by single blank lines. Each test case begins with a

line containing the integer n (2 ≤ n ≤ 350), the number of doors in the building. The following line

contains another integer, m (n − 1 ≤ m ≤ n(n − 1)/2), the number of sensors in the network. The

test case finishes with m lines containing a description of each of the m sensors. The i-th of those lines

contains three integers, a (0 ≤ a ≤ n−1), b (0 ≤ b ≤ n−1) and w (1 ≤ w ≤ 2

15), in that order. Integers

a and b represent the pair of doors controlled by the i-th sensor, and w its recommended voltage. You

can safely assume that there are no two sensors controlling the same two doors.

The input will finish with a line containing ‘0’.

Output

For each case, your program should output a line containing the minimum margin of an admissible

subset of the sensors.

Sample Input

3

3

0 1 220

1 2 120

2 0 160

4

5

2 3 80

1 3 80

0 1 180

2 1 200

3 0 140

0

Sample Output

40

60

 

 

【分析】

　　是Uva1395的进化版。

　　数据范围大了一点点，不过之前的方法也是够慢的，m^2。

　　总结来说，生成树问题其实就是有一棵最小生成树，然后你sm乱枚举一些东西，然后在最小生成树上搞啊搞。。【难道不是么？？..

　　最喜欢就是加一条边弄一个环然后在环上面又删一条边，就是没add边的时候两个点之间唯一路径上的边的权值求最值。

 

　　这题就是这样啦。

　　

　　先排序，加边，考虑一下加下去的边是否会形成环，如果形成环的话，就把环内的最小边去掉（因为最长边就是现在ADD的那条边，如果要苗条就让边最小尽量大），然后重新求这棵新的生成树的最小边。等到生成树形成的时候，因为添加进去的新边的权值肯定是最大值的，所以只要只减去之前维护一个的最小值就可以了。

　　然后，求路径最小边还有找最短边都是O（n）暴力的。

　　总时间复杂度：O（nm）

　　之前的方法复杂度是O（m^2）,嗯，很多恶心题就是完全图，如果是完全图的话，这样的方法无疑是更优的。

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 using namespace std; 9 #define Maxn 410 10 #define INF 0xfffffff 11 12 int n,m; 13 14 struct node 15 { 16 int x,y,c; 17 }t[Maxn*Maxn]; 18 19 bool cmp(node x,node y) { return x.c
            
           
          
         
        
       
      

 

WC这题代码把LA3887 A了！！！！

 

2016-11-02 09:52:33

 

--------------------------------------------------------------------------

突然发现这题是删边模版？