CEOI 2008 Day 1 Information

Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
47:12:26
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
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

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Benq

CEOI 2008 Day 1 Information

Автор Benq, история, 5 лет назад, По-английски

Does anyone have a $$$O(V^2)$$$ solution to this problem (available here)? The spoiler describes one but I don't understand what it means when it says to "search for this path backwards," and I can't find a model solution. (However, an $$$O(EV)$$$ solution with bitset did pass ...)

Benq
5 лет назад
5

Комментарии (5)

Написать комментарий?

youssefbou62

5 лет назад, # |

-49

Send $5500 and I'll help!

→ Ответить

tmz_IOI

5 лет назад, # |

+11

Not even one can answer Benq Question! Benqosity

→ Ответить

dacin21

5 лет назад, # |

← Rev. 2 →

+39

I don't have an easy solution, but the following paper provide (somewhat sophisticated) $$$O(V^2)$$$ solutions:

EDGE-DISJOINT SPANNING TREES, DOMINATORS, AND DEPTH-FIRST SEARCH by Robert E. Tarjan solves the problem in $$$O(V \log V + E)$$$ using dfs (the algorithm also computes the dominator tree).
A Matroid Approach to Finding Edge Connectivity and Packing Arborescences by Harold N. Gabow solves the problem of finding $$$k$$$ edge-disjoint Arborescences in $$$O(k^2 V^2)$$$. The algorithm is based on Matroid intersection theory and augmenting paths (and I don't know much about those topics).

→ Ответить