Rəngli yağış#994

Rəngli yağış (Həll təhlili)

Məsələ qonşuluq matrisi ilə verilmiş yönəlməmiş qrafın analizinə gətirilir.

Təpələr qrafın təpələri, körpülər isə onların arasındakı tillər kimi qəbul edilir. Qonşuluq matrisi $g [i] [j]$ g[i][j] $i$ və $j$ təpələri arasında körpünün olub-olmadığını göstərir. $i$ -ci təpənin rəngi $co l [i]$ massivinin xanasında verilmişdir.

Məsələdə "pis" körpülərin sayını tapmaq tələb olunur. Əgər körpü müxtəlif rəngli iki təpəni birləşdirirsə, yəni $(i, j)$ tili üçün $co l [i] \neq = co l [j]$ col[i] \ne col[j] şərti ödənirsə, o zaman körpü pis hesab olunur.

Qraf yönəlməmiş olduğundan, hər til yalnız bir dəfə nəzərə alınır, buna görə də yalnız $i \i, j)$ i \i, j) cütlükləri baxılır, burada $i < j$ i < j-dir.

Alqoritmin realizasiyası

$g$ qonşuluq matrisini və $co l$ rənglər massivini elan edək.

#define MAX 110
int g[MAX][MAX], col[MAX];

Qrafın qonşuluq matrisini oxuyuruq.

scanf("%d", &n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
  scanf("%d", &g[i][j]);

Təpələrin rəngləri massivini oxuyuruq.

for (i = 0; i < n; i++)
  scanf("%d", &col[i]);

$r es$ dəyişənində elə $(i, j)$ təpə cütlüklərinin sayını hesablayırıq ki, onların arasında körpü olsun ( $g [i] [j] = 1$ g[i][j] = 1) və $co l [i] \neq = co l [j]$ col[i] \ne col[j] şərti ödənsin.

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

Eyni cütlüyün iki dəfə (həm $(i, j)$ , həm də $(j, i)$ kimi) nəzərə alınmaması üçün son res qiymətini ikiyə bölmək lazımdır.

res /= 2;

Cavabı çap edirik.

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