• Зарегистрирован: 2012-04-10
  • Сообщений: 3

Тема: задача с графами

оригинал тут
http://www.codechef.com/problems/RG_01/
перевожу на рус.
дан связный неориентированный граф с весом. Определим цену пути между двумя вершинами, как наименьший вес ребра, входящего в данный путь. Для всех вершин необходимо найти максимальную цену пути. Надеюсь, объяснил понятно. Если нет - могу пояснить на примере позже.

Попробовал решить простым перебором - превышено время. То есть нужно заметить некую закономерность, которая поможет ускорить подсчет. Есть идеи у кого нибудь?

Мое решение в аттаче. Да, код кривой, знаю.

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: задача с графами

Отсортируем рёбра графа, и будем идти по ним в порядке от самых дорогих к самым дешёвым. Идея такая: на текущем шаге мы рассматриваем только рёбра с весом >= текущего, и мы смотрим, какие компоненты связности получаются из этих рёбер, и внутри каждой такой компоненты связности ответ между всеми парами вершин можно присвоить весу текущего ребра (только, понятно, для тех пар вершин, для которых ответ уже был найден ранее, обновлять его не надо).

Чтобы написать это за нормальную асимптотику, нужно явно хранить для каждой вершины номер её компоненты связности, и при рассмотрении текущего ребра смотреть: если оно соединяет вершины разных компонент, то эти две компоненты сливаются в одну, а ответ обновляется для всех пар вершин вида "(вершина_из_первой_компоненты;вершина_из_второй_компоненты)".

Итого будет решение за O(n^2) плюс предварительная сортировка за O(n^2 log n).

Сайтe-maxx

3 Ответ от wtq4er Отредактировано wtq4er (2012-05-14 11:20:17)

  • wtq4er
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-05-04
  • Сообщений: 8

Re: задача с графами

>нужно явно хранить для каждой вершины номер её компоненты связности
не совсем понятно, что представляет из себя "номер компоненты связности", как "компоненты связности" вообще нумеруются. можно второй абзац подробнее объяснить?

4 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: задача с графами

wtq4er пишет:

>нужно явно хранить для каждой вершины номер её компоненты связности
не совсем понятно, что представляет из себя "номер компоненты связности", как "компоненты связности" вообще нумеруются. можно второй абзац подробнее объяснить?

Изначально мы считаем, что рёбер нет, т.е. граф состоит просто из N вершин. Каждая вершина - в отдельной компоненте связности, т.е. component[ i ] = i (что означает "вершина номер i находится в компоненте с номером i"). Также для каждой компоненты давайте хранить, какие вершины в неё входят - это некий массив списков vertices, где изначально vertices[ i ] = [ i ] (что означает "i-ая компонента содержит единственную вершину i").

Теперь будем добавлять в граф по одному ребру, в порядке убывания их весов. Пусть текущее ребро - это ребро между вершинами x и y. Пусть cx = component[x], cy = component[y]. Тогда, если cx = cy, то это ребро ни на что не влияет. Если же cx != cy, то надо записать ответ для всех пар вершин вида vertices[cx][ i ] и vertices[cy][ j ]. Затем эти две компоненты cx и cy надо соединить в одну. Для этого мы проходимся по списку vertices[cy] и присваиваем для них component = cx; затем мы в конец списка vertices[cx] добавляем весь список vertices[cy].

Сайтe-maxx