算法 {生成树,最小生成树,Prim算法,Kruskal算法}
@LOC: 1
生成树spanning tree
;
前言: 图G, 图GG;
条件1: GG为G的生成子图;
条件2: GG是个树;
结论: GG为G的一个生成树;
@LINK: https://editor.csdn.net/md/?not_checkout=1&articleId=134386573
;
最小生成树Minimum Spanning Tree, MST
;
前言: 图G, 图GG; 一个生成树的权值等于(其所有边的权值和);
条件: GG为G的所有生成树中 权值最小的生成树;
结论: GG为G的一个最小生成树;
#前言#:
G
:
G:
G: 连通无向图;
M
:
M:
M: G中的某个最小生成树;
M
a
x
(
a
,
b
)
:
Max(a,b):
Max(a,b):
M
M
M中的a-b
路径里的边的最大值;
#性质#: 对于任意边
(
a
,
b
)
∈
G
(a,b) \in G
(a,b)∈G 且
∉
M
\notin M
∈/M, 其边权一定
≥
M
a
x
(
a
,
b
)
\geq Max(a,b)
≥Max(a,b); (否则, 用这条边替代
M
a
x
(
a
,
b
)
Max(a,b)
Max(a,b)后 得到更小的生成树);
@DELI;
#最小生成树的线性递增序列#
#前言#: S(x): 将生成树x的所有的边, 按照其边权递增排序后的*序列*
(可知所有的S(x)
的长度 均为N-1
, 因为所有生成树的边数都相同);
#性质#
1: 所有的最小生成树的S值(即边权递增序列), 是相同的;
2: 令最小生成树的序列为[a1, a2, ...]
, 则任意生成树的序列[b1, b2, ...]
一定满足
b
i
≥
a
i
b_i \geq a_i
bi≥ai;
. .
比如最小生成树的序列是[1, 2, 4]
, 则不会存在最小生成树为[2, 2, 3]
(这违反了性质1), 也不会存在生成树为[2, 3, 3]
(违反性质2), [1, 3, 4]
是可以的;
必须经过某些特定边的最小生成树;
MARK: @LOC_0
;
LINK: https://editor.csdn.net/md/?not_checkout=1&articleId=131996130
和Prim一样 也是动态增长的过程 每一次添加一条边, 但他不是以一棵树来增长的;
令图
T
=
(
V
,
∅
)
T = (V, \empty)
T=(V,∅) 即最开始 所有点都是孤立的(不连通的); 以边权递增的顺序 遍历所有的边 (a,b)
如果这两个点在T里是不连通的 则将该边添加到T中, 最终 T就变成了最小生成树;
namespace MST_Kruskal{
long long Work( int _pointsCount){
DisjointSet dSet( _pointsCount, _pointsCount);
long long ANS = 0;
for( 以边权*递增*的顺序遍历所有边(wth:边权, p1:端点, p2:端点)){
if( dSet.Get_root( p1) == dSet.Get_root( p2)){
continue;
}
dSet.Merge_to( p1, p2);
ANS += wth;
}
return ANS;
}
} // namespace MST_Kruskal
@DELI;
LINK: @LOC_0
Prim算法是一棵树渐渐长大的过程, 即第一次 是由1个点组成的树, 第二次 是由2个点组成的树, 第三次 是由3个点组成的树, …, 直至达到一个由 ∣ V ∣ |V| ∣V∣个点组成的树 就是最小生成树;
从第
i
i
i步(令
T
i
Ti
Ti为其对应的树) 转移到 第
i
+
1
i+1
i+1步(令
T
i
+
1
T_{i+1}
Ti+1为其对应的树), 那么这俩树之间 就差一个边 一个点;
令
E
E
EE
EE为 G里面的所有形如
(
a
,
b
)
(a,b)
(a,b) (
a
∈
T
i
,
b
∉
T
i
a \in T_i, b \notin T_i
a∈Ti,b∈/Ti)的边的集合, 令e为EE里边权最小的边, 则这个e 就是新添的这条边;
定义: 令SMT为所有最小生成树的集合;
.
一个树是合法的
⟺
\iff
⟺ 该树是SMT里的某个最小生成树的子树;
假如Prim算法 进行到第
i
i
i步时 此时当前的子树T是合法的, 但是添加了一个(a,b)
的边后 形成了TT树是不合法的;
.
令MT为SMT里的某个元素 且T是MT的子树; 令R为MT里抛去T之后的子树; 则T + R + (一个连接T-R的边) = MT
, 已知这个连接边 不是(a,b)
, 而且 他一定边权小于(a,b)
的边权; 我们将他替换成(a,b)
可知T + R + (a,b)
依然是个生成树 而且边权更小;
Dist[]
不是最短路径! 他是边权的最小值 (比如说所有边都是int
类型, 那么Dist[]
的类型 也是int
不需要是long long
)
.
比如{S}-(1)-a-(1)-b
S是当前维护的树, 此时Dist[a] = 1
, 而Dist[b]
是没有值的 因为没有从b
到{S}
的直接边, 路径不算的;
Prim算法的中间状态 他维护的一定是树, 而不是其他;
LINK: @LOC_0
namespace MST_Prim{
using __Edge_Type_ = int; // 图上边权的类型
static constexpr int __PointsCount_Maximum_ = 2003;
__Edge_Type_ __Distance[ __PointsCount_Maximum_];
bool __Vis[ __PointsCount_Maximum_];
long long Work( int _pointsCount){
//<
// #前设#: 令`G`为无向图;
// #返回值#: G的*所有连通分量*的最小生成树上所有边权之和;
// #pointsCount#: 无向图的所有点是`[0, _pointsCount)`范围;
// #提示#: 如果你想确保G必须是*连通的* (如果不是则报警) 其等价于: `LINK/@LOC_0`处只会进入*一次*;
ASSERT_( _pointsCount <= __PointsCount_Maximum_);
memset( __Distance, 0x7F, sizeof( __Edge_Type_) * _pointsCount);
auto invalid_distance = __Distance[ 0];
memset( __Vis, false, sizeof( bool) * _pointsCount);
long long ANS = 0;
for( int size = 1; size <= _pointsCount; ++size){
int new_point = -1;
for( int i = 0; i < _pointsCount; ++i){
if( ( __Vis[ i] == false) && ( __Distance[ i] != invalid_distance)){
if( new_point == -1 || __Distance[ i] < __Distance[ new_point]){ new_point = i;}
}
}
if( new_point == -1){ // MAKR/@LOC_0
for( int i = 0; i < _pointsCount; ++i){ if( __Vis[ i] == false){ new_point = i; break;}} __Distance[ new_point] = 0;
}
ANS += __Distance[ new_point];
__Vis[ new_point] = true;
for( `G中: new_point的所有邻接点nex 邻接边权值wth`){
if( false == __Vis[ nex]){
__Distance[ nex] = min( __Distance[ nex], wth);
}
}
}
return ANS;
}
} // namespace MST_Prim
#前言#:
[
V
1
≤
V
2
≤
.
.
.
]
:
[V1\leq V2 \leq ...]:
[V1≤V2≤...]: 任意生成树的权值一定为
V
i
V_i
Vi;
次小生成树为: 所有权值为
V
2
V2
V2的生成树;
#前言#:
M
:
M:
M:某一个最小生成树;
#性质#: 一定存在某个次小生成树 他的边集 与
M
M
M的边集, 只有1条边是不同的;
Given a Connected-Undirected-Graph with n n n points (it may contains Negative-Edge, Self-Loop, Negative-Loop, in other words, a arbitrary graph but satisfying Connected-Undirected), you need to find a Sub-Graph which contains n n n points, being connected and its weight (the sum of all edges) is minimal amongst others.
In fact, such a Sub-Graph could be a Tree (
n
−
1
n - 1
n−1 edges).
Because there may have many different Sub-Graph which share the same weight, we assert that there must exist a Tree amongst them.
There are some algorithms for getting a MST.
We have a tree T T T with a single arbitrary point originally, each time we add a point and a edge (which connects this new point and a point of T T T), after n − 1 n - 1 n−1 times we will get the MST.
We stipulate A d j E d g e s ( T ) AdjEdges( T) AdjEdges(T) is the set of all adjacent edges which connect a point of T T T and a point that is not belongs to T T T.
For example, the MST is
{b,...}
|
{c,...}-----a
|
{d,...}
+ the edges {d-c, d-f, d-e} are belong to MST.
+ {b,...} means a `Sub-Tree` of the MST, the same as {c,...} and {d,...}
Original, we set T = ( a ) T = (a) T=(a)
First time, (suppose that the weight of a − b a-b a−b is less than that of a − c a-c a−c and a − d a-d a−d), our goal is to get a − b a-b a−b, and then add it to T T T.
Property:
a
−
b
a-b
a−b is the minimal edge of
A
d
j
E
d
g
e
s
(
T
)
AdjEdges( T)
AdjEdges(T)
Because
a
−
b
a-b
a−b is less than
a
−
c
a-c
a−c and
a
−
d
a-d
a−d as we assumed, so we need to prove
a
−
b
a-b
a−b is less than any edge of
A
d
j
E
d
g
e
s
(
T
)
/
{
a
−
b
,
a
−
c
,
a
−
c
}
AdjEdges( T) / \{a-b, a-c, a-c\}
AdjEdges(T)/{a−b,a−c,a−c}
Proof:
T: {a}------{b,...}
|------{c,...}
|------{d,...}
if there exists a edge
a
−
B
a-B
a−B (
B
∈
{
b
,
.
.
.
}
B \in \{b,...\}
B∈{b,...}) which is less than
a
−
b
a-b
a−b, we can replace
a
−
b
a-b
a−b by
a
−
B
a-B
a−B to get a new-MST, however it has a smaller weight than the original-MST, so it raises a contradiction.
If there exists a edge
a
−
C
a-C
a−C (
C
∈
{
c
,
.
.
.
}
C \in \{c,...\}
C∈{c,...}) which is less than
a
−
b
a-b
a−b, we can also replace
a
−
c
a-c
a−c by
a
−
C
a-C
a−C to get a smaller new-MST which also makes a contradiction.
More generally, if
T
T
T contains multiple points, e.g.,
{
a
,
x
,
y
}
\{a, x, y\}
{a,x,y}. Now, the edge
?
−
b
?-b
?−b means there is a edge between
?
?
? (a point of
T
T
T) and
b
b
b in the MST.
Supposing
?
−
b
?-b
?−b is less than
?
−
c
,
?
−
d
?-c, ?-d
?−c,?−d, and you can also prove that
?
−
b
?-b
?−b is the minimal edge of
A
d
j
E
d
g
e
(
T
)
AdjEdge( T)
AdjEdge(T).
Therefore, the process of Prim is consisted of n n n steps:
We will use a auxiliary array Distance to finish this algorithm.
Assume that T = ( a , b , c ) T = (a, b, c) T=(a,b,c) at current and others undetermined points are ( d , e , f ) (d, e, f) (d,e,f), then D i s t a n c e [ d ] = m i n ( E d g e [ d − a ] , E d g e [ d − b ] , E d g e [ d − c ] ) Distance[ d] = min( Edge[d-a], Edge[d-b], Edge[d-c]) Distance[d]=min(Edge[d−a],Edge[d−b],Edge[d−c]), that is, the D i s t a n c e Distance Distance of a undetermined point x x x is the minimal edge of all edges which connect x x x and a point of T T T.
Next, we iterate all undetermined points (d, e, f), find the minimal D i s t a n c e Distance Distance (suppose it is d d d), then d d d is added to T T T, and D i s t a n c e [ d ] Distance[d] Distance[d] is a new edge of MST.
Finally, because
d
d
d is belongs to
T
T
T, so
D
i
s
t
a
n
c
e
[
e
]
=
m
i
n
(
E
d
g
e
[
e
−
a
]
,
E
d
g
e
[
e
−
b
]
,
E
d
g
e
[
e
−
c
]
)
Distance[ e] = min( Edge[e-a], Edge[e-b], Edge[e-c])
Distance[e]=min(Edge[e−a],Edge[e−b],Edge[e−c]) should also be updated by
E
d
g
e
[
e
−
d
]
Edge[e-d]
Edge[e−d].
… that is, iterate all undetermined points (e,f), update
D
i
s
t
a
n
c
e
[
x
]
=
m
i
n
(
s
e
l
f
,
E
d
g
e
[
x
,
d
]
)
Distance[ x] = min( self, Edge[ x, d])
Distance[x]=min(self,Edge[x,d]). (
d
d
d is the new point that added into MST).
Auxiliary-Property-1:
For a graph, its MST must contains
e
e
e which is the minimal edge of the graph.
(proof: e.g., a--b--c
is a branch of MST, and there exists a edge a-c
that is the minimal edge amongst all edges of the graph; then you can replace a--b
by a-c
to make the MST more optimal)
Auxiliary-Property-2:
For a graph (contains
(
a
,
b
,
c
,
d
,
e
)
(a,b,c,d,e)
(a,b,c,d,e) points), when we divide its MST into two partition, e.g., if
c
−
d
c-d
c−d is a edge of MST, then remove this edge, we will get two Sub-Tree of MST (denote
M
1
,
M
2
M1, M2
M1,M2), let it be
(
a
,
b
,
c
)
(a,b,c)
(a,b,c) and
(
d
,
e
)
(d,e)
(d,e). And also divide this graph into two partition (denote
G
1
,
G
2
G1, G2
G1,G2): one contains
(
a
,
b
,
c
)
(a,b,c)
(a,b,c) points and its interior edges, another contains
(
d
,
e
)
(d,e)
(d,e) points and its interior edges.
Then,
M
1
M1
M1 is also the MST of
G
1
G1
G1, the same as
M
2
,
G
2
M2, G2
M2,G2.
(proof: if
m
m
m is the MST of
G
1
G1
G1 instead of
M
1
M1
M1, then the Tree
m
,
(
c
−
d
)
,
m
2
m, (c-d), m2
m,(c−d),m2 is also a MST which is less than the previous MST, this is contradictory.)
Originally, let e d g e s edges edges be all edges of the graph. Stipulate m i n ( e d g e s ) min( edges) min(edges) denotes the minimal-edge of e d g e s edges edges.
As a result, sort all edges at first, and iterate each edge
(
a
,
b
,
w
)
(a,b,w)
(a,b,w), if
a
,
b
a, b
a,b are not in a same Disjoint-Set, then
w
w
w is a edge of MST (the removal-edge as mentioned above), then Merge
a
,
b
a, b
a,b to the same Set.
Otherwise
a
,
b
a,b
a,b is in the same Set, meaning the operation that remove a edge that connects two divided-Graph (
G
(
a
)
,
G
(
b
)
G(a), G(b)
G(a),G(b) as mentioned above)
+
The edges of the graph in Prim or Kruskal, are both undirected (bidirectional).
+
If the graph is not connected, that is consists of several connected-subgraphs
G
0
,
G
i
,
.
.
.
G0, Gi, ...
G0,Gi,... (where
G
0
G0
G0 denotes a connected-subgraph that contains point-
0
0
0), Prim can only get the MST of
G
0
G0
G0 not for
G
i
,
.
.
.
Gi, ...
Gi,...; while Kruskal could get all MSTs of
G
0
,
G
i
,
.
.
.
G0, Gi, ...
G0,Gi,... simultaneously.
+
Prim, Kruskal can also be used to calculate Maximal-ST, by replacing
m
i
n
min
min by
m
a
x
max
max.
.
Proof: ???
+
For a undirected-graph
G
G
G, when you storing it
.
In Prim, for any undirected-edge (a,b,w)
(assume there is no other edges between (a,b)
), you must make sure Edges[a][b] = Edges[b][a] = w
in the Adjacency-Matrix. That is, one undirected-edge corresponds to two directed-edges.
.
In Kruskal, you can just choose one directed-edge (a->b)
to be stored in Linked-List, not necessary both sides; this is due to the mechanism of Kruskal (the disjoint-set not relates the direction of edges) Consequently, one undirected-edge just corresponds to its one directed-edge is enough.
Let MST be the edges e 1 , e 2 , . . . e m e1, e2, ...em e1,e2,...em, then all inferior-MST (strictly, or non-strictly) must be the edges f 1 , f 2 , . . . , f m f1, f2, ..., fm f1,f2,...,fm where only one pair of edges e i ≠ f j ei \neq fj ei=fj, in other words, if we remove e i , f j ei, fj ei,fj, the rest two sets will form a bijection.
Let the context of the next discussion be Strictly Inferior-MST.
If we have a MST
e
1
,
e
2
,
.
.
.
,
e
m
e1, e2, ..., em
e1,e2,...,em, then we iterator all edges on
G
G
G which are not
e
i
ei
ei (i.e., the edges not in the MST)
For any such a edge
f
i
fi
fi (if its endpoints are
a
,
b
a, b
a,b, and the path of them in the MST are
e
x
,
e
y
,
e
z
ex, ey, ez
ex,ey,ez, the weight are
3
,
5
,
5
3, 5, 5
3,5,5)
There is a necessity:
f
i
≥
5
fi \geq 5
fi≥5 (if not, that is
f
i
<
5
fi < 5
fi<5, we move
5
5
5 from MST and add
f
i
fi
fi, it again forms a ST whose sum less than MST;) this is a property of MST, which is no matter to inferior-MST.
.
According to the property above, if the inferior-MST contains
f
i
fi
fi, then the edges of inferior-MST must be obtained by the process: remove a edge
e
x
/
e
y
/
e
z
ex/ey/ez
ex/ey/ez from MST, and then add
f
i
fi
fi
There are also some lemmas on the relationship between the removal edge and
f
i
fi
fi.
1
when
f
i
>
5
fi > 5
fi>5, only if
f
i
fi
fi replace the maximal edge
5
5
5, that could maybe the inferior-MST (because if
f
i
fi
fi replace
1
/
3
1/3
1/3, it will get a much large ST than replacing
5
5
5)
2
otherwise
f
i
=
5
fi = 5
fi=5, if the inferior-MST is strictly, then we shall try to use
f
i
fi
fi to replace the strictly inferior-maximal edge
3
3
3 (although there are multiple same maximal edges
5
5
5; e.g., the MST is
3
,
5
,
5
3, 5, 5
3,5,5 and there is only one edge
5
5
5 which not belongs to MST, so all STs with distinct sum are
3
,
5
,
5
3,5,5
3,5,5 and
5
,
5
,
5
5,5,5
5,5,5; that is, now we should choose the strictly inferior-maximal-edge
3
3
3 on the MST-path, not the non-strictly
5
5
5)
That is, we need get d 1 d1 d1 means the maximal edge of the path a − b a - b a−b in MST, d 2 d2 d2 means the strictly inferior-maximal edge in that path (note that, if the path is 3 , 5 , 5 3, 5, 5 3,5,5, then d 1 = 5 , d 2 = 3 d1 = 5, d2 = 3 d1=5,d2=3, that is the case of strictly inferior-MST)
Suppose all edges are ≥ 0 \geq 0 ≥0 and we use − 1 -1 −1 denotes a invalid-edge;
Strictly-Inferior-MST
//> get the maximal and inferior-maximal edges on the path (a-b) in the MST
pair< int, int> Get_edges( int a, int b){
d1 = d2 = -1; //< d1 is the maximal-edge, d2 is the inferiore-maximal
for( auto w : Edges on the path `a-b` in MST){
if( _w > d1){
d2 = d1, d1 = _w;
}
else if( _w < d1){
d2 = max( _w, d2);
}
}
}
//----
//> find the Strictly-Inferior-MST
ans = 0x7F7F7F7F...;
for( edge `(a-b):w` : all edges of the graph ){
if( this edge on the MST){
continue;
}
if( a == b){
continue;
}
pair ret = Get_edges( a, b);
ASSERT_( ret.first != -1);
if( w > ret.first){
ans = min( mst_size - ret.first + w, ans);
}
else if( ret.second != -1){
ans = min( mst_size - ret.second + w, ans);
}
}
Non-Strictly-Inferior-MST
//> get the maximal edge on the path (a-b) in the MST
pair< int, int> Get_edges( int a, int b){
d1 = -1; //< d1 is the maximal-edge
for( auto w : Edges on the path `a-b` in MST){
d1 = max( d1, w);
}
}
//----
//> find the NonStrictly-Inferior-MST
ans = 0x7F7F7F7F...;
for( edge `(a-b):w` : all edges of the graph ){
if( this edge on the MST){
continue;
}
if( a == b){
continue;
}
auto ret = Get_edges( a, b);
ASSERT_( ret != -1);
ans = min( mst_size - ret + w, ans);
}
Cuz there are only N = 500 N = 500 N=500 points, when we got the MST, we can use D 1 [ N ] [ N ] , D 2 [ N ] [ N ] D1[N][N], D2[N][N] D1[N][N],D2[N][N] denotes the Maximal and Inferior-Maximal edge on the path ( a − b ) (a-b) (a−b) in the MST. More precisely, let D f s ( x ) Dfs(x) Dfs(x) to get all D 1 [ x ] [ a l l ] , D 2 [ x ] [ a l l ] D1[x][all], D2[x][all] D1[x][all],D2[x][all], then performing D f s ( a l l ) Dfs( all) Dfs(all)
Due to
N
=
1
e
5
N = 1e5
N=1e5, the above
N
2
N^2
N2 device is infeasible here.
Cuz MST is a tree, we can use LCA algorithm which will divide a path
a
−
b
a-b
a−b into several disjoint segments (is also a path essentially)
s
1
,
s
2
,
.
.
.
s1, s2, ...
s1,s2,..., then we can store
d
1
,
d
2
d1, d2
d1,d2 which represent the maximal and inferior-maximal edge for each segment
s
i
si
si, then we gather them up
(
d
1
,
d
2
)
(
d
1
,
d
2
)
.
.
.
(d1, d2) (d1, d2) ...
(d1,d2)(d1,d2)... and the maximal and inferior-maximal edge on the path
a
−
b
a-b
a−b must be contained in this set.
//> building `dist1, dist2`
for( int power = 0; power < power_range; ++power){
if( power == 0){
ptrNew_father[ nex][ power] = cur;
dist1[ nex][ power] = wth;
dist2[ nex][ power] = -1;
continue;
}
int mid = ptrNew_father[ nex][ power - 1];
if( (mid == -1) || (ptrNew_father[ mid][ power - 1] == -1)){
ptrNew_father[ nex][ power] = -1;
dist1[ nex][ power] = -1;
dist2[ nex][ power] = -1;
continue;
}
ptrNew_father[ nex][ power] = ptrNew_father[ mid][ power - 1];
int _edges[ 4] = { dist1[ nex][ power - 1], dist2[ nex][ power - 1],
dist1[ mid][ power - 1], dist2[ nex][ power - 1]};
sort( _edges, _edges + 4);
dist1[ nex][ power] = _edges[ 3];
dist2[ nex][ power] = -1;
for( int i = 2; i >= 0; --i){
if( _edges[ i] != dist1[ nex][ power]){
dist2[ nex][ power] = _edges[ i];
break;
}
}
ASSERT_( dist2[ nex][ power] < dist1[ nex][ power]);
}
//----
//> get the maximal and inferior-maximal edges on the path (a-b) in MST.
pair< int, int> Get_edges( int _a, int _b){
int d1 = -1, d2 = -1;
ASSERT_( (_a >= 0) && (_a < ptrRef_tree->Get_pointsCount()));
ASSERT_( (_b >= 0) && (_b < ptrRef_tree->Get_pointsCount()));
if( ptrNew_depth[ _a] != ptrNew_depth[ _b]){
if( ptrNew_depth[ _a] < ptrNew_depth[ _b]){
swap( _a, _b);
}
for( int i = power_range - 1; i >= 0; --i){
if( ptrNew_father[ _a][ i] == -1){
continue;
}
if( ptrNew_depth[ ptrNew_father[ _a][ i]] >= ptrNew_depth[ _b]){
update( d1, d2, dist1[ _a][ i]);
update( d1, d2, dist2[ _a][ i]);
_a = ptrNew_father[ _a][ i];
}
}
}
ASSERT_( ptrNew_depth[ _a] == ptrNew_depth[ _b]);
if( _a == _b){
return {d1, d2};
}
for( int i = power_range - 1; i >= 0; --i){
if( ptrNew_father[ _a][ i] != ptrNew_father[ _b][ i]){
update( d1, d2, dist1[ _a][ i]); update( d1, d2, dist2[ _a][ i]);
update( d1, d2, dist1[ _b][ i]); update( d1, d2, dist2[ _b][ i]);
//--
_a = ptrNew_father[ _a][ i];
_b = ptrNew_father[ _b][ i];
}
}
ASSERT_( ptrNew_father[ _a][ 0] == ptrNew_father[ _b][ 0]);
update( d1, d2, dist1[ _a][ 0]); update( d1, d2, dist2[ _a][ 0]);
update( d1, d2, dist1[ _b][ 0]); update( d1, d2, dist2[ _b][ 0]);
return {d1, d2};
}
void update( int & d1, int & d2, int _w){
if( _w > d1){
d2 = d1;
d1 = _w;
}
else if( _w != d1){
d2 = max( _w, d2);
}
}