当前位置:网站首页>Black dot = = white dot (MST)

Black dot = = white dot (MST)

2022-06-25 08:02:00 Mfy's little brother 1

Black spot == White spot (MST)

The question :

Let's give a connected graph with no phase , Each edge may be black or white , Ask if there is a spanning tree structure that makes the number of black edges on the tree == Number of white edges

2 ≤ n ≤ 1 e 5 , 1 ≤ m ≤ 1 e 5 2\leq n\leq1e5,1\leq m\leq 1e5 2n1e5,1m1e5
Ideas :

1. Regard the black edge weight as 1, The weight of the white edge is regarded as 0, For any value between the minimum spanning tree and the maximum spanning tree edge weight sum , There are corresponding spanning trees

2. Obvious : One of the minimum spanning trees 0 Edge deletion , Then the minimum spanning tree weight is at most +1, thus , For any value between the minimum spanning tree and the maximum spanning tree edge weight sum , There are corresponding spanning trees .

( Isn't this a doll ? So it's obvious : )

原网站

版权声明
本文为[Mfy's little brother 1]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/176/202206250624540177.html