Перекрестки в
городе соединены односторонними дорогами. Напишите программу, которая вычисляет
количество разных путей между каждой парой перекрестков. Путем называется
последовательность односторонних дорог, соединяющих перекрестки.
Перекрестки
обозначаются неотрицательными целыми числами. Односторонняя дорога обозначается
парой перекрестков, которые она соединяет. Например, j k указывает на то, что
односторонняя дорога идет от перекрестка j
к перекрестку k. Заметим, что
двусторонняя дорога может быть промоделирована двумя односторонними: j k
и k j.
Рассмотрим город
с четырьмя перекрестками, которые соединены улицами следующим образом:
0 1
0 2
1 2
2 3
Существует
только один путь между перекрестками 0 и 1, два пути между 0 и 2 (это 0 ® 1 ® 2 и 0 ® 2), два пути между 0 и 3, один путь между 1 и 2, один путь
между 1 и 3, один путь между 2 и 3, других путей не существует.
Возможно, между
некоторыми перекрестками существует бесконечное количество путей. Например, если
к описанному выше множеству дорог добавить 3 2, между 0 и 1 останется один путь,
но появится бесконечное количество путей между 0 и 2. Потому что из 2 в 3 и
назад из 3 в 2 можно двигаться произвольное количество раз, получая бесконечное
количество разных путей. То есть пути 0 ® 2 ® 3 ® 2 ® 3 ® 2 и 0 ® 2 ® 3 ® 2 разные.
Вход. Первое число содержит количество односторонних улиц в
городе, за которым следует их описание. Каждая улица задается парой
перекрестков, которые она соединяет: каждая пара j k представляет собой
одностороннюю улицу от перекрестка j к
перекрестку k. Во всех городах
перекрестки последовательно пронумерованы с 0 до “наибольшего” перекрестка. Все
целые числа во входных данных разделены между собой одним пробелом.
Ни одна из
односторонних улиц не ведет от перекрестка к нему же самому. Город не может иметь
более 30 перекрестков.
Выход. Вывести квадратную матрицу, содержащую
информацию о количестве разных путей между перекрестками j и k. Если обозначить
выводимую матрицу через M, то M[j][k] – это количество разных путей,
ведущих от перекрестка j к
перекрестку k. Матрицу M выводить
построчно, в порядке возрастания строк.
Если между двумя
перекрестками существует бесконечное количество путей, вывести -1. Не
беспокойтесь о выравнивании выходных данных при печати матрицы. Все выводимые
числа в строках матриц должны
разделяться одним пробелом.
|
Пример
входа 1 |
Пример
выхода 1 |
|
7 0 1 0 2 0
4 2 4 2 3 3 1 4 3 |
0 4 1 3 2 0 0 0 0 0 0 2 0 2 1 0 1 0 0 0 0 1 0 1 0 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
9 0 1 0 2 0 3 0 4 1 4 2 1 2 0 3 0 3 1 |
-1 -1 -1 -1
-1 0 0 0 0 1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 0 0 0 0 0 |
графы –
алгоритм Флойда - Уоршела
Анализ алгоритма
Если между i - ой и k - ой вершиной существует m[i][k] путей, а между k - ой и j - ой вершиной
m[k][j] путей, то количество путей между i - ой и j - ой вершиной,
проходящих через k - ую вершину,
равно m[i][k] * m[k][j]. При помощи алгоритма Флойда –
Уоршела вычисляем количество путей между i
- ой и j - ой вершиной.
Между вершинами i и j
существует бесконечное количество путей, если существует такая вершина k, что одновременно существуют пути из i в k,
из k в k, из k в j. При этом вершины i, j, k могут совпадать. Если между вершинами i и j
существует бесконечное количество путей, то установим m[i][j] = –1.
Реализация алгоритма
Матрицу
смежности графа храним в массиве m.
#define MAX 30
int m[MAX][MAX];
Функция FloydWarshall реализует алгоритм Флойда – Уоршела и вычисляет
количество путей между вершинами i и j при отсутствии циклов. Но даже если в
графе присутствуют циклы, но между вершинами i
и j существует конечное количество
путей, то оно будет занесено в m[i][j].
void FloydWarshall(void)
{
int i, j, k;
for(k = 0; k
<= v; k++)
for(i = 0; i
<= v; i++)
for(j = 0; j
<= v; j++)
m[i][j] += m[i][k] * m[k][j];
}
Основная часть программы. Читаем входные данные и строим
входной граф. В переменной v
вычисляем количество вершин в графе. Нам известно, что перекрестки
последовательно пронумерованы с 0 до “наибольшего” перекрестка.
scanf("%d",&n); memset(m,0,sizeof(m));
for(v = i = 0; i < n; i++)
{
scanf("%d
%d",&a,&b); m[a][b] = 1;
if (a > v)
v = a; if (b > v) v = b;
}
Запускаем алгоритм Флойда – Уоршела,
вычисляем количество путей между парами вершин.
FloydWarshall();
Займемся обработкой циклов. Находим все такие вершины k, для которых существует путь из k в k.
При этом если существуют пути из i в k и из k в j, то между i и j
существует бесконечное количество путей. Устанавливаем m[i][j] = –1.
for(k = 0; k <= v; k++)
if(m[k][k])
for(i = 0; i <= v; i++)
for(j = 0; j
<= v; j++)
if(m[i][k]
&& m[k][j]) m[i][j] = -1;
Выводим результирующую матрицу,
которая содержит количество разных путей между перекрестками.
for(i = 0; i <= v; i++)
{
printf("%d",m[i][0]);
for(j = 1; j
<= v; j++)
printf("
%d",m[i][j]);
printf("\n");
}