Gara delle mucche#10151

Gara delle mucche (Editoriale)

Dichiariamo una matrice booleana $g$ . Per ogni coppia di mucche $a$ e $b$ impostiamo $g [a] [b] = t r u e$ g[a][b] = true, se la mucca $a$ vince contro la mucca $b$ . In questo modo, tracciamo un arco orientato da $a$ a $b$ . Poiché i risultati dei round sono coerenti, il grafo costruito è aciclico.

Il rango della mucca con numero $i$ può essere determinato se per ogni altra mucca $j$ è noto quale delle due sia più forte: o la mucca $i$ può battere la mucca $j$ (eventualmente attraverso diverse mucche intermedie), oppure la mucca $j$ può battere la mucca $i$ . In altre parole, nella chiusura transitiva del grafo, per ogni coppia $i$ e $j$ deve essere soddisfatta almeno una delle condizioni: $g [i] [j] = t r u e$ g[i][j] = true oppure $g [j] [i] = t r u e$ g[j][i] = true.

Allo stesso tempo, entrambi i valori $g [i] [j]$ g[i][j] e $g [j] [i]$ g[j][i] non possono essere uguali a $t r u e$ , poiché ciò significherebbe la presenza di una contraddizione nei risultati delle gare.

Esempio

Nell'esempio riportato, è possibile determinare in modo univoco i ranghi solo per le mucche $2$ e $5$ .

La mucca $2$ vince contro la mucca $5$ , ma perde contro tutte le altre mucche. La mucca $5$ perde contro tutte le altre mucche.

Per la mucca $1$ non è noto se riuscirà a battere le mucche $3$ e $4$ . Analogamente, per le mucche $3$ e $4$ non è noto se riusciranno a battere la mucca $1$ . Pertanto, non è possibile determinare i ranghi esatti di queste mucche.

Implementazione dell'algoritmo

Dichiariamo una matrice booleana $g$ .

bool g[101][101];

Leggiamo i dati in input.

scanf("%d %d", &n, &m);

Consideriamo che ogni mucca vince contro sé stessa.

for (i = 1; i <= n; i++) g[i][i] = 1;

Leggiamo i dati in input. Costruiamo il grafo di input. Se la mucca $a$ ha vinto contro la mucca $b$ , tracciamo un arco da $a$ a $b$ .

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = 1;
}

Calcoliamo la chiusura transitiva del grafo. Se dal vertice $i$ al vertice $j$ esiste un percorso lungo gli archi del grafo, impostiamo $g [i] [j] = t r u e$ g[i][j] = true.

for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
  if (g[i][k] && g[k][j]) g[i][j] = true;

Nella variabile $r es$ accumuliamo il numero di mucche per le quali è possibile determinare in modo univoco il rango.

res = 0;

In un ciclo, verifichiamo a turno ogni mucca e stabiliamo se sia possibile determinare in modo univoco il suo rango.

for (i = 1; i <= n; i++)
{

Verifichiamo se è possibile determinare il rango della mucca con numero $i$ . Per farlo, esaminiamo tutte le mucche $j$ . Se per una qualche mucca sono soddisfatte entrambe le condizioni: $g [i] [j] = f a l se$ g[i][j] = false e $g [j] [i] = f a l se$ g[j][i] = false, allora non è possibile stabilire quale delle due mucche sia più forte. Di conseguenza, non è possibile determinare il rango esatto della mucca con numero $i$ .

  bool good = true;
  for (j = 1; j <= n; j++)
    if (g[i][j] == false && g[j][i] == false)
    {
      good = false;
     break;
    }

C++

Se dopo aver verificato tutte le mucche il valore di $g oo d$ rimane uguale a $t r u e$ , significa che per la mucca $i$ la sua posizione rispetto a ogni altra mucca è nota. Di conseguenza, il suo rango può essere determinato in modo univoco.

  if (good) res++;
}

Stampiamo la risposta.

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