Форум программистов, компьютерный форум CyberForum.ru

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

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

какой алгоритм использовать? IDEAS? - C++

11.04.2013, 03:04. Просмотров 264. Ответов 1
Метки нет (Все метки)

ЗАДАЧА:

С целью подготовки к проведению олимпиады по информатике мэр решил обеспечить надежным электроснабжением все школы города. Для этого необходимо провести линию электропередач от альтернативного источника электроэнергии "ГРЭС" к одной из школ города (к какой неважно), а также соединить линиями электропередач некоторые школы между собой.
Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником " ГРЭС ", либо с одной из тех школ, которые имеют надежное электроснабжение. Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения (стоимость схемы равняется сумме стоимостей соединений пар школ).
Напишите программу, которая вычисляет стоимость двух наиболее экономных схем альтернативного электроснабжения школ.
Входные данные
В первой строке входного файла находятся два натуральных числа, разделенных пробелом: N (3≤N≤100), количество школ в городе, и M - количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci - стоимость прокладки линии электроснабжения (1≤Ci ≤300) от школы Ai до школы Bi (i = 1, 2, ..., N).
Выходные данные
В единственной строке выходного файла должны содержаться два натуральных числа S1 и S2, разделенных пробелом - две наименьшие стоимости схем (S1 ≤ S2). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.
Пример

input.txt output.txt
5 8 110 121
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

Добавлено через 40 секунд
Напишите код
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.04.2013, 03:04     какой алгоритм использовать? IDEAS?
Посмотрите здесь:

какой алгоритм использовать - C++
Просьба подсказать как решить эту задачу. Имеются данные в файле в таком виде: Необходимо их привести к такому виду: Я не...

Какой тип использовать? - C++
В какой тип нужно преобразовать int, что бы вывести через TextOut? Пытался через wchar_t, потом пробовал через TextOutA и через char, но...

Когда какой контейнер использовать? - C++
Поделитесь опытом, когда и при каких условиях какой контейнер особенно удобен? Только поменьше абстракции пожалуйста :)

Какой отладчик лучше использовать? - C++
Привет всем. Скажите, какой отладчик лучше использовать начинающему?

Какой стек технологий использовать - C++
Всем доброго времени суток! Хочу написать программу для черчения. Если быть точнее, то что-то в корне похожее на AutoCAD, но основная...

Какой контейнер для чего использовать? - C++
для чего какой контейнер эффективней использовать? vector- list- map- set- queue- stack-

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

Какой вариант конструктора использовать правильней? - C++
Два примера кода, какой из них использовать более корректно и профессионально? 1) card(){ } card (deck_1 value_1, deck_2...

Какой контейнер в STL и для чего эффективнее использовать? - C++
Какой контейнер в STL и для чего эффективнее использовать? И почему

Какой тип использовать для создания рекрсивного массива - C++
Здравствуйте. Не в первый раз встречаюсь с различными задачами в которых очень удобно было бы использовать универсальный тип...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
11.04.2013, 03:17     какой алгоритм использовать? IDEAS? #2
Алгоритм Прима. Пошёл сам и написал.
Ответ Создать тему
Опции темы

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