994. Цветной дождь

В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение “зован”. На следующий день выпал цветной дождь, причем он прошел только над холмами. В некоторых местах падали красные капли, в некоторых – синие, а в остальных – зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся. Посчитайте количество таких “плохих” мостов.

Вход. В первой строке записано число холмов n (0 < n ≤ 100). Далее идет матрица смежности, описывающая наличие мостов между холмами (1-мост есть, 0-нет). В последней строке записано n чисел, обозначающих цвет холмов: 1 – красный; 2 – синий; 3 – зеленый.

Выход. Вывести количество “плохих” мостов.

Пример входа	Пример выхода
7 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 3 3	4

РЕШЕНИЕ

графы

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

Система холмов и мостов задает граф. Пусть g[i][j] – его матрица смежности. Пусть цвет i-го холма равен col[i]. В задаче следует подсчитать количество таких пар холмов (i, j) (i < j), между которыми есть мост (g[i][j] = 1) и для которых col[i] ≠ col[j].

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

Объявим матрицу смежности g и массив цветов col.

#define MAX 110

int g[MAX][MAX], col[MAX];

Читаем матрицу смежности графа.

scanf("%d", &n);

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

for (j = 0; j < n; j++)

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

Читаем массив цветов холмов.

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

scanf("%d", &col[i]);

Подсчитываем в переменной res количество таких пар холмов (i, j), между которыми есть мост (g[i][j] = 1) и для которых col[i] ≠ col[j]. Чтобы пары (i, j) и (j, i) не считать как разные, их результирующее количество res следует поделить пополам.

res = 0;

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

for (j = 0; j < n; j++)

if (g[i][j] == 1 && col[i] != col[j]) res++;

res /= 2;

Выводим ответ.

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