Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
#1

Поиск минимального цикла - C++

09.01.2014, 17:17. Просмотров 439. Ответов 5
Метки нет (Все метки)

Очень надеюсь, не ошибусь в терминах.
Имеется полный неориентированый взешенный граф. Вводится числ Н, потом идет матрица смежности НхН, значения которой являются весом ребер. Размер графа равен НхН и инициализируется после ввода числа Н. 1 < H < 100. 1 < Вес ребра < 1000
Ну и вопрос такой же, как и в заголовке - вывести минимальный (самый легкий, короткий) цикл. Выводить цикл вершинами. (1,2,3)
P.S. Таких финтефлюшек, которые их себя в себя, в этом графе нету, то есть в главной диагонали стоят нолики.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.01.2014, 17:17
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Поиск минимального цикла (C++):

Поиск минимального гамильтонова цикла в матрице - C++
#include &lt;iostream&gt; using namespace std; #define n 10 int c ; // номер хода, на котором посещается вершина int path; // номера...

Поиск минимального элемента - C++
Доброго времени суток. Помогите пожалуйста с программой, вот задание: В одномерном массиве, состоящим из n вещественных элементов,...

Поиск минимального значения - C++
Здравствуйте подскажите пожалуйста, как сделать поиск минимального значения. Дано 5 формул типа z=8*x+y*2. Нужно вывести наименьший...

Поиск минимального элемента в массиве - C++
Помогите решить задачку,Вводим в ручную массив и в нем нужно найти минимальные элемент Заранее спасибо

Быстрый поиск минимального числа - C++
подскажите быстрый алгоритм поиска второго минимального числа в массиве?

Поиск минимального элемента матрицы - C++
Люди добрые помогите пожалуйта написать программу на С++ Задан двухмерный массив целых чисел A размером N на M. Найти минимальный элемент...

5
ya_noob
_
314 / 148 / 9
Регистрация: 08.10.2011
Сообщений: 432
09.01.2014, 17:57 #2
Domonion, классная задача, она имеет красивое решение с помощью алгоритма флойда. если знаком с иероглифами, то вот http://tadvent.wordpress.com/2009/02/14/最小环-与-floyd/ . можешь еще на тимусе почитать форум к этой задаче: http://acm.timus.ru/problem.aspx?space=1&num=1004
0
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
09.01.2014, 18:32  [ТС] #3
Цитата Сообщение от ya_noob Посмотреть сообщение
Domonion, классная задача, она имеет красивое решение с помощью алгоритма флойда. если знаком с иероглифами, то вот http://tadvent.wordpress.com/2009/02/14/最小环-与-floyd/ . можешь еще на тимусе почитать форум к этой задаче: http://acm.timus.ru/problem.aspx?space=1&num=1004
Я не понял решения у китайцев.

Добавлено через 4 минуты
Дай мне, пожалуйста, код нормальный. Я просто не понимаю, как та программа относится к моей задаче.

Добавлено через 15 минут
UP, задачу к 21-00 по МСК надо сдать сегодня.
0
ya_noob
_
314 / 148 / 9
Регистрация: 08.10.2011
Сообщений: 432
09.01.2014, 19:05 #4
Цитата Сообщение от Domonion Посмотреть сообщение
задачу к 21-00 по МСК надо сдать сегодня.
до часа Ч еще 2 часа, есть время разобраться. по китайской ссылке сам алгоритм и написан, правда он ищет только длину цикла, но чуть чуть подумав, можно прикрутить к нему вывод вершин (там всё легко, всего лишь надо запомнить 3 ключевые точки).
Цитата Сообщение от Domonion Посмотреть сообщение
Я просто не понимаю, как та программа относится к моей задаче.
значит вы не разобрались с задачей. подумайте (1) из чего состоит цикл, (2) чем может пригодиться матрица путей, полученной из алгоритма флойда, и (3) какие 3 точки являются ключевыми для построения цикла.
PS: сначала покажите, что вы что-то понимаете в задаче (3 вопроса выше), а уж потом я подумаю давать вам решение задачи или нет.
0
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
09.01.2014, 19:58  [ТС] #5
Цитата Сообщение от ya_noob Посмотреть сообщение
до часа Ч еще 2 часа, есть время разобраться. по китайской ссылке сам алгоритм и написан, правда он ищет только длину цикла, но чуть чуть подумав, можно прикрутить к нему вывод вершин (там всё легко, всего лишь надо запомнить 3 ключевые точки).

значит вы не разобрались с задачей. подумайте (1) из чего состоит цикл, (2) чем может пригодиться матрица путей, полученной из алгоритма флойда, и (3) какие 3 точки являются ключевыми для построения цикла.
PS: сначала покажите, что вы что-то понимаете в задаче (3 вопроса выше), а уж потом я подумаю давать вам решение задачи или нет.
Цикл - путь, начинающийся и кончающийся в одной и той же точке, при условии, что ни одна точка не повторяется.
В этой программе цикл будет состоять из начальной точки, первой точки и самого короткого путя из 1 точки в начальную. Матрица путей нам как раз и пригодится для поиска последнего. А 3 вопрос не понимаю просто. 3 вершины или 3 точки программы?
0
ya_noob
_
314 / 148 / 9
Регистрация: 08.10.2011
Сообщений: 432
09.01.2014, 20:42 #6
Цитата Сообщение от Domonion Посмотреть сообщение
Цикл - путь, начинающийся и кончающийся в одной и той же точке, при условии, что ни одна точка не повторяется.
В этой программе цикл будет состоять из начальной точки, первой точки и самого короткого путя из 1 точки в начальную. Матрица путей нам как раз и пригодится для поиска последнего. А 3 вопрос не понимаю просто. 3 вершины или 3 точки программы?
флойд строит лес кратчайших путей из каждой вершины. цикл будет состоять из 2 кратчайших путей из некоторой корневой вершины (1-ая точка) до других 2-х вершин (2-я и 3-я точки) (причем эти пути не имеют общих вершин, кроме корневой), а также те 2 вершины соединяются ребром.

ладно, скину тебе в личку решение той задачи с тимуса (надеюсь ты понял, что там такая же задача)

Добавлено через 14 минут
получил?
0
09.01.2014, 20:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.01.2014, 20:42
Привет! Вот еще темы с ответами:

Поиск минимального элемента в матрице - C++
Помогите решить задачку,Вводим в ручную матрицу и в нем нужно найти минимальные элемент спасибо

Поиск в массиве минимального элемента - C++
Ребят помогите. дан массив n*n. нужно найти в каждом столбце минимальный элемент и записать данные в новый массив. подтолкните на путь...

Поиск минимального числа в файле - C++
Здравствуйте, прошу помогите. По заданию надо сделать программу которая будет искать минимальное значение в каждой строке файла, а затем...

Поиск вектора, минимального по длине - C++
Даны m векторов х1 = (х11, х21, ...,хn1), ..., xm = (x1m, x2m, ...,xnm). Написать программу поиска вектора минимального по длине. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru