10987. Антифлойд

В офисе компании имеется n компьютеров, соединенные в сеть m каналами. Каждый кабель соединяет два компьютера. Любые два компьютера соединены не более одним кабелем. Каждый кабель имеет латентность в микросекундах, означающий время передачи данных по нем. Маршрутизация в сети устроена так, что передача данных от компьютера А к компьютеру В происходит за наименьшее латентное время. Кабели двунаправленные, их латентное время одинаково в обоих направлениях.

Вы – новичок в компании и хотите определить какие компьютеры связаны друг с другом и с каким латентным временем. Вскоре Вы обнаружили что это сложная работа, так как в здании много этажей, а кабели спрятаны в стенах. Тогда Вы решили от каждого компьютера послать сообщение каждому и измерили каждую из n * (n – 1) / 2 латентностей. По этой информации Вам следует найти латентность каждого кабеля. При вычислениях Вы хотите получить наименьшее возможное количество кабелей.

Вход. Первая строка содержит количество тестов N. Каждый тест начинается строкой, содержащей значение n (0 < n < 100). Следующие n – 1 строка содержит результаты измерений. i-ая строка содержит i целых чисел в промежутке [1, 10000]. j-ое целое число равно латентному времени, за которое сообщение проходит от компьютера i + 1 к j (и назад).

Выход. Для каждого теста вывести его номер в формате “Case #x:”. Следующая строка содержит количество кабелей m. Каждая из следующих m строк содержит три целых числа: u, v и w, означающих тот факт что между компьютерами u и v латентность равна w. Выводимые строки следует отсортировать по u, потом по v, при этом u < v. Если существует несколько решений, то подойдет любое. Если ситуация невозможна, вывести “Need better measurements.”. После каждого теста следует выводить пустую строку.

Пример входа

2

3

100

200 100

3

100

300 100

Пример выхода

Case #1:

2

1 2 100

2 3 100

Case #2:

Need better measurements.

РЕШЕНИЕ

Флойд - Уоршел

Анализ алгоритма

Занесем результат измерений в массив с, помня что c[i][j] = c[j][i]. Если существуют такие индексы i, j, k, что c[i][k] + c[k][j] < c[i][j], то измерения не корректны и следует вывести “Need better measurements.”. Если c[i][k] + c[k][j] = c[i][j], то канал между i и j лишний, и его можно удалить. Для проверки этих двух условий запускаем обычный алгоритм Флойда-Уоршела с тройным вложенным циклом.

Результирующее количество кабелей равно количеству ненулевых элементов среди c[i][j], где например i < j. Далее выводим эти значения согласно требуемого формата.

Реализация алгоритма

scanf("%d",&tests);

for(cs = 1; cs <= tests; cs++)

{

Читаем входные данные для каждого теста.

scanf("%d",&n);

memset(c,0,sizeof(c));

for(i = 2; i <= n; i++)

for(j = 1; j < i; j++)

scanf("%d",&c[i][j]), c[j][i] = c[i][j];

Запускаем тройной цикл Флойда – Уоршела, в теле которого проверяем два выше описанных условия. Устанавливаем flag = 1 в случае неверных измерений.

flag = 0;

for(k = 1; k <= n; k++) if (!flag)

for(i = 1; i <= n; i++) if (!flag)

for(j = 1; j <= n; j++) if (!flag)

{

if ((i == k) || (j == k) || (i == j)) continue;

if (!c[i][k] || !c[k][j] || !c[i][j]) continue;

if (c[i][k] + c[k][j] < c[i][j]) flag = 1;

if (c[i][k] + c[k][j] == c[i][j]) c[i][j] = c[j][i] = 0;

}

printf("Case #%d:\n",cs);

if (flag) printf("Need better measurements.\n"); else

{

Вычисляем количество кабелей cables.

cables = 0;

for(i = 2; i <= n; i++)

for(j = 1; j < i; j++)

cables += (c[i][j] > 0);

printf("%d\n",cables);

Выводим данные о соединениях.

for(i = 1; i <= n; i++)

for(j = i + 1; j <= n; j++)

if (c[i][j]) printf("%d %d %d\n",i,j,c[i][j]);

}

printf("\n");

}