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

Покрашенный граф - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти число элементов массива > T и их произведение. http://www.cyberforum.ru/cpp-beginners/thread424211.html
Недоработанная прога: #include <iostream.h> #include <conio.h> int Proiz_Kol(int,int,int**,int*); void main() { int **a, i, j, n, m, pr, kol; cout<<"\t Input N, M:";
C++ Перегрузка оператора "=" Дано такое задание Ввести строку символов S1. Программа должна содержать перегруженную операцию “=”, использование которой скопирует S1 в S2 при следующих условиях:Подстроку в квадратных “” скобках.... http://www.cyberforum.ru/cpp-beginners/thread424204.html
Измените программу с использованием циклических алгоритмов C++
Для каждого x, изменяющегося от a до b с шагом h, найти значения функции Y(x), суммы S(x) и |Y(x)–S(x)| и вывести в виде таблицы. Значения a, b, h и n вводятся с клавиатуры. Работу программы...
C++ Матрицы в С. Очень нужна ваша помощь
Помогите решить хотя бы некоторые задачи, а я на их примере буду кумекать над остальными. Просто 11го экзамен по программированию, а я ни бум бум. Заранее огромное спасибо Выкладывайте сами...
C++ Функции: подсчет годовой зарплаты работника http://www.cyberforum.ru/cpp-beginners/thread424146.html
Задача: Известна ежемесячная заработная плата персонала предприятия в течение календарного года. Вывести фамилии тех сотрудников, у которых годовая заработная плата выше средней. Считать, что штат...
C++ Задачник по C++ со всеми уровнями сложности подскажите задачник по с++ со всеми уровнями сложности подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.01.2012, 23:23
Niсe, У Вас реализацию поиска в ширину. Для этой задачи любой существующий алгоритм в оригинальном виде не подойдет. Нужно переделывать его под эту задачу.
Представьте себе вершину (допустим через нее проходит самый короткий путь) - в которую входят 3 дуги (по одной каждого цвета) и из которой выходят 3 дуги (по одной каждого цвета). Допустим Вы дошли быстрее всего в эту вершину через дугу цветом 1. Вы ее помечаете, и идете дальше по двум дугам: 2 и 3 цветов. Путь в эту же вершину через дугу 2 хоть и дольше чем через дугу 1, но он дает возможность идти дальше из этой вершины по дуге 1 и в итоге может оказаться что это и есть самый короткий путь.
Для этой задачи подойдет поиск в ширину, но:
- рассматривайте вершину не как единое целое, а как три разных составляющих (по цветам). Например вершину 4, рассматривайте как: (4,1), (4,2), (4,3). Здесь второе число считается номером цвета. Для каждой такой составляющей будет свое значение. Например: (4,1)=15, (4,2)=15, (4,3)=17. Это будет значить, что вершину 4 по дугам 1 и 2 цвета мы достигли за 15 шагов, а по дуге цветом 3, мы достигли за 17 шагов.
Изначально помещайте в очередь не просто вершину n-1, а вот так: (n-1,1), (n-1,2), (n-1, 3), поставив им метки 0 (будем считать, что вершину, из которой начинаем путь мы по всем вершинам достигли за 0 шагов).
Далее алгоритм такой:
Из очереди берете очередной элемент, например: (4,2). Смотрите смежные вершины с 4 вершиной, (например смежная вершина 3). Если смежная вершина соединена не дугой цветом 2 (например цветом 1), то: (3,1), если она не помечена, помечаете значением (4,2)+1 и заносите в очередь.
В конце этого алгоритма проверяете значения (0,1), (0,2), (0,3). Если все три значения не помечены, то ответ: -1. Если нет, то ответ минимальное значение из трех.
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru