0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
|
|
1 | |
Непростая задача на графы.06.05.2012, 15:11. Показов 3143. Ответов 10
Метки нет (Все метки)
Здравствуйте! Необходимо решить такую задачу:
Антон работает в межгалактическом туристическом агентстве. Довольно часто ему приходится прокладывать путь с одной планеты на другую с использованием существующих рейсов космических кораблей. К сожалению, количество рейсов невелико, поэтому пассажирам часто приходится пересаживаться на промежуточных планетах. Антон заметил, что некоторые планеты используются в качестве промежуточных чаще, чем другие. Он решил провести исследование – для каждой планеты A он хотел бы узнать, сколько существует пар различных планет (B,C), таких что любой путь с планеты B на планету C проходит через планету A. Помогите Антону! Входные данные Первая строка входного файла INPUT.TXT содержит два целых числа: N и M – количество планет и количество рейсов космических кораблей, соответственно (2 <= N <= 20 000, 1 <= M <= 200 000). Следующие M строк описывают рейсы космических кораблей. Каждый рейс связывает две планеты, и им можно воспользоваться в любом из двух направлений. С любой планеты можно добраться до любой другой. Выходные данные В выходной файл OUTPUT.TXT выведите N целых чисел – для каждой планеты A выведите количество пар различных планет, таких что любой путь с одной планеты на другую проходит через A. Уже долго мучаюсь с этой задачей. По-моему алгоритм решения таков: находим в данном графе точки сочленения, потом для каждой найденной точки удаляем все ребра исходящие из него, находим количество элементов в каждой получившейся компоненте связности и вычисляем количество пар вершин в этих компонентах. Если вершина не является точкой сочленения, то количество пар вершин равно N-1. Реализация данного алгоритма заваливается на первых тестах из=за неверного ответа. В чем я неправ?
0
|
06.05.2012, 15:11 | |
Ответы с готовыми решениями:
10
Задача на графы задача про графы Логическая задача (графы) Интересная задача на графы |
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
06.05.2012, 16:28 | 2 |
Вы в ответ для таких вершин выводите N-1 ? Тогда это неправильно, для таких вершин ответ 0.
Что Вы выводите в ответ в этом случае? И еще один вопрос: вы удаляете ребра окончательно для каждой точки сочленения (при просмотре других точек, Вы эти ребра уже не учитываете?)
1
|
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
|
||||||
06.05.2012, 18:27 [ТС] | 3 | |||||
7 9 1 2 1 3 1 4 1 5 1 6 1 7 2 3 4 5 6 7 соответствует ответ 18 6 6 6 6 6 6 Может быть я что-то неправильно понял?
Кстати, на этом форуме я нашел тему в которой Вы выложили эту задачу. Вы ее все-таки решили?)
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
06.05.2012, 23:54 | 4 | |||||
Вы все правильно поняли.
правильнее будет вернуть:
Лучше покажите весь код. Кстати, насколько я помню, в этой задаче тяжело было уложиться по времени. да.
0
|
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
|
||||||
07.05.2012, 20:44 [ТС] | 5 | |||||
Выкладываю весь код. Не судите строго, программист я начинающий)
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
08.05.2012, 05:40 | 6 |
Потестировал Ваш код:
на тест: вот эта функция: при удалении точки 1, выдает что имеется 4 компоненты связности (должно быть 3) и все имеют размер 2 А например при тесте: 4 3 1 2 2 3 3 4 функция: выдает что точек сочленения всего 1 (должно быть 2) Но даже если исправить ошибки, то по времени у Вас не получится пройти. Я вспомнил эту задачу и посмотрел свой код - у меня всего два прохода в глубину. Уже на втором проходе вывод результата для каждой вершины. Если интересует мой вариант, могу описать алгоритм.
2
|
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
|
|
08.05.2012, 18:59 [ТС] | 7 |
Да, действительно, недочетов много... Спасибо, что указали ошибки.
Уложиться всего в два обхода в глубину? Интересно, даже очень)
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
08.05.2012, 20:56 | 8 | |||||
Если коротко то так:
заводим 4 массива: int res[N] - для хранения результатов int a[N] - метки вершин при достижении их в глубину (которые остаются без изменений) int b[N] - метки вершин при достижении их в глубину (которые будут меняться) bool mas_kontr[N] - помечать уже пройденные вершины. Заводим глобальную переменную int time=0; Считываем входные данные и делаем первый проход в глубину (с помощью рекурсии). Первая рекурсивная функция выглядит так:
после первого прохода, снова приводим массив mas_kontr[] к первоначальному виду (он еще будет участвовать во втором проходе в глубину) и вызываем вторую рек.функцию: int rec2(int n) { // помечаем вершину n в mas_kontr[] как пройденную int v=1, tmp2=0, tmp1; // перебираем вершины смежные с n // очередная смежная вершина X не помечена, как пройденная { tmp1=rec2(X); if(b[X]==b[n]) { res[n]+=(N-v-tmp1)*tmp1; v+=tmp1; } else tmp2+=tmp1; } res[n]+=N-1; return v+tmp2; } ее вызов rec2(0); все. Потом вывод значений из res[].
1
|
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
|
||||||
09.05.2012, 14:10 [ТС] | 9 | |||||
Хм, интересно. Вот полный листинг программы по вашему алгоритму.
17 9 0 0 0 0 0
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
09.05.2012, 17:44 | 10 | |||||
1
|
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
|
|
09.05.2012, 19:55 [ТС] | 11 |
Да, очень остроумно) Эдакая модифицированная программа по нахождению точек сочленения.
Спасибо Вам большое, valeriikozlov, за то что Вы не жалея времени помогаете людям.
0
|
09.05.2012, 19:55 | |
09.05.2012, 19:55 | |
Помогаю со студенческими работами здесь
11
Задача про графы Задача на графы. Удалить ребро, соединяющее вершины a и b Несложная задача на графы - возможная утечка памяти Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0 Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |