994. Colored rain

At Banana Republic there is a lot of hills, connected by bridges. At a chemical plant accident occurred, resulting in evaporated experimental fertilizer “summons”. The next day fell colored rain, and it was just over the hills. In some places red drops fell, in some blue, and the rest drops are green, and the hills were colored. President of Banana Republic is pleased, but he wants to paint the bridges between the tops of hills so that the bridges will be painted in the colors of the hills it connects. Unfortunately, if the bridge connects the hills of different colors, then painting will not succeed. Find the number of such “bad” bridges.

Input. The first line contains the number of hills n (0 < n ≤ 100). Then given an adjacency matrix describing the presence of bridges between the hills (1 – bridge exists, 0 – no bridge). The last line contains n numbers giving the color of the hills: 1 – red, 2 – blue, 3 – green.

Output. Print the number of “bad” bridges.

Sample input	Sample output
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

SOLUTION

graphs

Algorithm analysis

The system of hills and bridges defines the graph. Let g[i][j] be its adjacency matrix. Let the color of the i-th hill be col[i]. In the problem you must calculate the number of pairs of hills (i, j) (i < j), between which there is a bridge (g[i][j] = 1) and for which col[i] ≠ col[j].

Algorithm realization

Declare an adjacency matrix g and an array of colors col.

#define MAX 110

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

Read the adjacency matrix of the graph.

scanf("%d", &n);

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

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

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

Read the array of hill colors.

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

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

Count in the variable res the number of such pairs of hills (i, j), between which there is a bridge (g[i][j] = 1) and for which col[i] ≠ col[j]. To avoid counting pairs (i, j) and (j, i) as different, the resulting number res should be halved.

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;

Print the answer.

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