Кольоровий дощ (Розбір)

Задача зводиться до аналізу неорієнтованого графа, заданого матрицею суміжності.

Холми розглядаються як вершини графа, а мости — як ребра між ними. Матриця суміжності g[i][j] показує, чи існує мост між вершинами $i$ та $j$. Колір $i$-го холма заданий у ячейці масиву $col[i]$.

У задачі необхідно знайти кількість "поганих" мостів. Мост вважається поганим, якщо він з'єднує два холми різного кольору, тобто якщо для ребра $(i,j)$ виконується умова col[i] \ne col[j].

Оскільки граф неорієнтований, кожне ребро враховується один раз, тому розглядаються лише пари $(i,j)$, де $i\text{<}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] \ne col[j].

res = 0;
for (i = 0; i \< n; i++)
for (j = 0; j \< n; j++)
  if ((g[i][j] == 1) \&\& (col[i] != col[j])) res++;

Щоб не враховувати одну й ту саму пару двічі (як $(i,j)$ та $(j,i)$), підсумкове значення res слід розділити на два.

res /= 2;

Виводимо відповідь.

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