| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
Здравствуйте , хотелось бы узнать , существует ли алгоритм, с помощью которого можно было бы вычислить количество остовных деревьев в заданном графе быстрее чем за O(n^3) как это указано тут : http://e-maxx.ru/algo/kirchhoff_theorem ?
Заранее спасибо !
Если граф полный, то можно быстрее: ответ равен n(n - 2).
Или может Ваш граф чем другим примечателен?
Можно даже расширить класс графов :-)
Пусть G = Kn - {e1, e2..., em}. Тогда, чтобы свести задачу к полному графу, достаточно использовать формулу: Ans(G) = Ans(G + e1) - Ans(G / e1). Где (+) — это добавление ребра в граф, а (/) — стягивание концов ребра в одну вершину.
Итого O(n + 2m).
Например, можно находить определитель матрицы Кирхгофа быстрее чем за O(n^3).
Там ведь очень просто :)
Три раза прочитал пост и нигде не увидел чтобы требовалось просто
Минус тридцать один! Раньше, если послать кого-то, то так не минусовали. Офигеть...
Поведай как, пожалуйста.
Ну есть же модные способы подсчета определителя за O(n^2.376). В википедии даже ссылочка на статью есть, где описан этот способ. Я, правда, сомневаюсь, что в реальных задачах его можно использовать, но вопрос был про сложность "быстрее чем за O(n^3)"...
А вообще, что-то мне подсказывает, что автор топика хочет решить задачу, где нужно найти количество остовных деревьев в графе, который состоит из циклов и простых путей (с одной идущей сейчас олимпиады). Пусть он меня поправит, если это не так:)
Ясно, я подумал есть что хорошее для матричек нужного нам вида.