Змагання корів#10151

Змагання корів (Розбір)

Оголосимо булеву матрицю $g$ . Для кожної пари корів $a$ і $b$ встановимо $g [a] [b] = t r u e$ g[a][b] = true, якщо корова $a$ перемагає корову $b$ . Таким чином, проведемо орієнтоване ребро від $a$ до $b$ . Оскільки результати раундів несуперечливі, побудований граф є ациклічним.

Ранг корови з номером $i$ можна визначити, якщо для будь-якої іншої корови $j$ відомо, яка з них сильніша: або корова $i$ може перемогти корову $j$ (можливо, через кілька проміжних корів), або корова $j$ може перемогти корову $i$ . Іншими словами, у транзитивному замиканні графа для кожної пари $i$ і $j$ повинна виконуватися хоча б одна з умов: $g [i] [j] = t r u e$ g[i][j] = true або $g [j] [i] = t r u e$ g[j][i] = true.

Одночасно обидва значення $g [i] [j]$ g[i][j] і $g [j] [i]$ g[j][i] не можуть дорівнювати $t r u e$ , оскільки це означало б наявність протиріччя в результатах змагань.

Приклад

У наведеному прикладі можна однозначно визначити ранги лише для корів $2$ і $5$ .

Корова $2$ перемагає корову $5$ , але програє всім іншим коровам. Корова $5$ програє всім іншим коровам.

Для корови $1$ невідомо, чи зможе вона перемогти корів $3$ і $4$ . Аналогічно, для корів $3$ і $4$ невідомо, чи зможуть вони перемогти корову $1$ . Тому точні ранги цих корів визначити неможливо.

Реалізація алгоритму

Оголосимо булеву матрицю $g$ .

bool g[101][101];

Зчитуємо вхідні дані.

scanf("%d %d",

Вважаємо, що кожна корова перемагає саму себе.

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

Зчитуємо вхідні дані. Будуємо вхідний граф. Якщо корова $a$ перемогла корову $b$ , проводимо ребро від $a$ до $b$ .

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

Обчислюємо транзитивне замикання графа. Якщо з вершини $i$ у вершину $j$ існує шлях по ребрах графа, встановлюємо $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]

У змінній $r es$ накопичуємо кількість корів, для яких можна однозначно визначити ранг.

res = 0;

У циклі по черзі перевіряємо кожну корову і з'ясовуємо, чи можна однозначно визначити її ранг.

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

Перевіримо, чи можна визначити ранг корови з номером $i$ . Для цього переберемо всіх корів $j$ . Якщо для якоїсь корови виконуються обидві умови: $g [i] [j] = f a l se$ g[i][j] = false і $g [j] [i] = f a l se$ g[j][i] = false, то неможливо визначити, яка з двох корів сильніша. Отже, точний ранг корови з номером $i$ визначити не можна.

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

C++

Якщо після перевірки всіх корів значення $g oo d$ залишилося рівним $t r u e$ , значить, для корови $i$ її положення відносно кожної іншої корови відоме. Отже, її ранг можна однозначно визначити.

  if (good) res++;
}

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

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