Hi, I have a question related to MST.
Suppose that we are given a graph where we have limited knowledge of the edge weights: Example
Is it possible to find all edges that are contained in at least one MST?
Thank you...
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
22:25:52
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
22:25:52
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 19:09:09 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
The problem statement is unclear. Are we to decide if an edge exists in a MST for all possible configurations of the question marks? Or if that edge exists in a MST for at least one possible configuration?
In either case it is possible to modify Kruskal's algorithm.
Question mark means there is an edge but length of the edge is unknown!
Well yeah, but in that case there are edges which might be in at least one MST if the unknowns have favorable valuables, but which might also not be in a MST. Should we include those edges?
I guess we should not
We will first find out whether each edge with a known weight definitely exists in some MST, then whether each edge with an unknown weight definitely exists in some MST. Both cases can be handled with a modified variant of Kruskal's algorithm.
The worst case is when as many as possible edges with unknown values are in a MST. Let's make a DSU and add all the unknown edges to it. Now let's sort the edges with known weights by their weights and start processing the edges in blocks of equal weight. For each edge in a block, check if its endpoints are in different connectivity components (with the DSU), but don't merge them yet. If an edge's endpoints are in different connectivity components, the edge definitely exists in a MST. Once you've processed all the edges in a block, merge their endpoints in the DSU.
Now for the edges with unknown weights. Make a new DSU and merge the endpoints of all edges with known weights. An edge with an unknown weight definitely exists in at least one MST if its endpoints are in different connectivity components in the DSU.
The complexity of the first part is
; the complexity of the second part is 
, so the total complexity comes down to 
.
I believe what it means is that for each edge we need to determine if it's included in some MST, for any possible weights of the edges of the question marks.
For that we could just immediately give all these edges a weight 0.
Your comment is as ambiguous as the statement, but I see what you mean because of the weight 0 thing. Anyway we still need to consider when the edges with unknown weights are in any MST.