| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Задача на графах |
| Автор: Fixin 9.1.2004, 19:33 |
| Тут такое дело, может поможет кто? Решил сделать задачку, но ума видно нехватает: "В некоторой стране есть развитая сеть железных дорог. С доисторических времён и до нашего времени в стране непрерывно происходят военные перевороты, из-за которых в системе железнодорожного транспорта этой страны происходят непрерывные изменения. Дело в том, что во время очередного переворота некоторые дороги разрушаются из-за военных действий, а пока новый правитель некоторое время находится у власти, он восстанавливает часть дорог. Временами железнодорожная система в этой стране становилась довольно разветвленной, поэтому некоторые города могли быть соединены двумя и более дорогами. Кроме того, дорога могла начинаться и заканчиваться в одном и том же городе, причем для одного города таких дорог могло быть несколько. Инженер Джио проводит испытания новых сверхскоростных поездов. Поскольку поезда экспериментальные, у них не должно возникать трудностей при проезде через промежуточные города. Поэтому инженер Джио требует, чтобы ни в каком городе на пути поезда, кроме, может быть, начального и конечного, не было развилок. Точнее, из любого промежуточного города на пути поезда должны выходить либо ровно две дороги, ведущие в другие города (возможно, в один и тот же), либо ровно одна дорога, начинающаяся и заканчивающаяся в этом городе. Естественно, что Джио желает испытать поезд на максимальной возможной скорости, и поэтому после каждого изменения в системе путей он хочет знать максимальную длину пути, по которому может ехать поезд. Поскольку в доисторические времена не умели добывать железо, в начале никаких дорог между городами нет. В первой строке входного файла находятся целые положительные числа 1< n<500 - число городов в стране, и 1<m<50000 - число изменений в железнодорожной системе. В следующих m строках находится информация об изменениях состояния системы путей. Каждое изменение является либо добавлением дороги, либо удалением дороги. В случае добавления дороги в очередной строке записан ноль, а затем идут три целых числа. Первые два из них являются номерами городов, соединяемых дорогой, а последнее является длиной добавленной дороги. Города нумеруются целыми числам от 1 до n. Длина дороги является целым положительным числом, не превосходящим 10^6. В случае удаления дороги в очередной строке сначала записана единица, а затем идёт номер шага, на котором произошло добавление удаляемой дороги. Для каждого изменения системы путей выведите в очередную строку выходного файла символ `*', если после очередного изменения системы путей существует сколь угодно длинный путь, удовлетворяющий условиям, поставленным Джио. В противном случае выведите в выходной файл единственное целое число, являющееся длиной максимального возможного пути. Входнае данные: 5 16 0 2 3 4 0 3 4 3 0 1 2 1 0 5 5 4 1 1 1 4 0 4 1 4 0 4 5 1 0 1 4 1 1 7 0 1 5 7 1 2 1 3 1 8 1 9 1 11 Выходные: 4 7 8 * * 3 8 5 4 3 8 9 * 8 7 0 Я подумал, что можно-бы исполизовать как основной объект не вершину (город), а ребро (жд) и записывать все данные о связи в структуру: class tLink { private: int CitiA; int CitiB; int Len; int Stp; //шаг создания }; Тогда связи от каждого города можно разложить на дерево, но с ним я работать не умею. Подскажите кто-нибудь! |
| Автор: mr.DUDA 9.1.2004, 23:47 |
| имхо, топик нужно переместить в "Алгоритмы". |
| Автор: Fixin 10.1.2004, 21:51 | ||
А как это сделать? Точнее там она есть, нужно бы убрать эту. |