| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [c++]задача на графы |
| Автор: girlsbest 22.5.2010, 20:45 |
| Помогите пожалуйста с написанием задачи, что-то ничего не выходит. Условие Предположим, что есть страна с N городами. Дана система магистралей, соединяющая напрямую города между собой. Длина любого прямого соединения равна 1. Система магистралей называется «четно-нечетной», если любые два города, соединены и путем четной длины, и путем нечетной длины. Необходимо определить является ли система магистралей «четно-нечетной» или нет. Если ответ на вопрос отрицательный, то найти одно из подмножеств множества городов, в котором максимальное количество элементов, и которое удовлетво-ряет следующему условию: если какие-либо два города из этого подмножества соединены путем, то его длина - четна. Входные данные Входные данные находятся в файле input.txt. · Первая строка содержит число городов N (N≤300). · Следующие N строк файла задают магистрали: i+1 строка файла содержит номера городов, которые связаны напрямую с городом i (если таких городов нет, то строка содержит ноль, числа в строке разделены пробелами). Выходные данные Выходные данные находятся в файле output.txt. Если система магистралей является четно-нечетной, то файл содержит единственную строку YES. Если нет, то первая строка содержит сообщение NO, а вторая строка содержит мощность одного из максимальных по мощности подмножеств X. Пример 1 входных данных 5 2 5 3 1 2 4 3 5 4 1 Пример 1 выходных данных YES |