Pioggia colorata#994

Pioggia colorata (Editoriale)

Il problema si riduce all'analisi di un grafo non orientato, definito da una matrice di adiacenza.

Le colline sono considerate come i vertici del grafo, e i ponti — come gli archi tra di essi. La matrice di adiacenza $g [i] [j]$ g[i][j] indica se esiste un ponte tra i vertici $i$ e $j$ . Il colore della $i$ -esima collina è specificato nella cella dell'array $co l [i]$ .

Nel problema è necessario trovare il numero di ponti "cattivi". Un ponte è considerato cattivo se collega due colline di colore diverso, cioè se per l'arco $(i, j)$ è soddisfatta la condizione $co l [i] \neq = co l [j]$ col[i] \ne col[j].

Poiché il grafo è non orientato, ogni arco viene considerato una sola volta, quindi si considerano solo le coppie $(i, j)$ dove $i \< j$ .

Implementazione dell'algoritmo

Dichiariamo la matrice di adiacenza $g$ e l'array dei colori $co l$ .

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

Leggiamo la matrice di adiacenza del grafo.

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

Leggiamo l'array dei colori delle colline.

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

Contiamo nella variabile $r es$ il numero di tali coppie di colline $(i, j)$ , tra le quali esiste un ponte ( $g [i] [j] = 1$ g[i][j] = 1) e per le quali $co l [i] \neq = co l [j]$ 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++;

Per non considerare la stessa coppia due volte (come $(i, j)$ e $(j, i)$ ), il valore finale di res dovrebbe essere diviso per due.

res /= 2;

Stampiamo la risposta.

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