Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Вопрос-Ответ Новый топик    Ответить
 Помогите решить задачу  [new]
h869311
Member

Откуда:
Сообщений: 236
Помогите решить задачу

http://acm.timus.ru/problem.aspx?space=1&num=1072

Имеется сеть из нескольких компьютеров, с настроенной по правилам TCP/IP маршрутизацией. Это означает, что:
Каждый компьютер имеет 1 или более сетевых интерфейсов;
Каждый интерфейс идентифицируется IP-адресом и маской подсети — это два 4-х байтных числа, разделённые точками через каждый байт, причём в двоичном представлении маска подсети выглядит следующим образом: сначала идёт k единиц, потом m нулей, k + m = 8*4 = 32. (Например, 212.220.35.77 — IP-адрес, 255.255.255.128 — маска).
2 компьютера относятся к одной подсети, если (IP1 AND NetMask1) = (IP2 AND NetMask2), где IPi и NetMaski — IP-адрес и маска i-го компьютера, AND — побитовое умножение.
Пакет между компьютерами, находящими в одной подсети передаётся непосредственно.
Пакет между компьютерами, находящимися в 2-х разных подсетях, проходит через компьютеры, имеющие интерфейсы, подключенные к нескольким подсетям, причём при переходе из подсети в подсеть компьютер, на котором осуществляется этот переход, должен иметь интерфейсы, относящиеся к обеим подсетям.
Задача состоит в том, чтобы найти кратчайший путь пакета между двумя указанными компьютерами.
Исходные данные
В первой строке стоит число N — количество компьютеров в сети, далее идёт N секций, описывающих интерфейсы каждого компьютера. В первой строке секции стоит число K — количество интерфейсов этого компьютера, затем следуют K строк с описанием интерфейсов в виде пар IP-адресов и масок. В последней строке стоят номера двух компьютеров, между которыми надо найти путь.
Известно, что 2 ≤ N ≤ 90 и K ≤ 5.
Результат
Если путь существует, выведите «Yes» и в следующей строке через пробел номера компьютеров, через которые проходит путь. Если такого пути не существует, выведите «No».

исходные данные

6
2
10.0.0.1 255.0.0.0
192.168.0.1 255.255.255.0
1
10.0.0.2 255.0.0.0
3
192.168.0.2 255.255.255.0
212.220.31.1 255.255.255.0
212.220.35.1 255.255.255.0
1
212.220.31.2 255.255.255.0
2
212.220.35.2 255.255.255.0
195.38.54.65 255.255.255.224
1
195.38.54.94 255.255.255.224
1 6


результат
Yes
1 3 5 6
30 авг 12, 18:47    [13091137]     Ответить | Цитировать Сообщить модератору
 Re: Помогите решить задачу  [new]
Abstraction
Member

Откуда:
Сообщений: 2342
h869311,

1) По исходным данным построить граф связей.
2) По графу связей найти кратчайший путь.
30 авг 12, 23:11    [13092048]     Ответить | Цитировать Сообщить модератору
 Re: Помогите решить задачу  [new]
AndreTM
Member

Откуда: Где-то в вологодских лесах...
Сообщений: 6901
Реально - это отвязаться от понятий "компьютеры" и "компьтерная сеть", а перейти к графам.

С другой стороны, эта задача также легко решается эмуляцией маршрутизаторов в каждом узле: т.е. вместо построения графа - за первый проход строится "правильная" таблица маршрутизации на каждом узле (в реальной жизни Route Table и так существует), а за второй - строится маршрут...
Что от вас и требуется по условию задачи...

Но и ведь же маршрутизация в сетях - только частное приложение теории графов...
31 авг 12, 01:30    [13092408]     Ответить | Цитировать Сообщить модератору
Все форумы / Вопрос-Ответ Ответить