CEOI 2008 Day 1 Information

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

Автор 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).

→ Ответить