Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя yahooo

Флойд
Автор yahooo, 13 лет назад, По-русски

не объясните как писать флойда за V^3 div k, в частности я слышал, что можно за V^3  div 32? я конечно понимаю, что гугл хорошая штука, но ничего по этому поводу я так и не нашел...

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится
Никак. За такую асимптотику можно находить транзитивное замыкание орграфа. Алгоритм и правда крайне похож на алгоритм Флойда.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

    спасибо

    P.S жаль только прямой эфир засрал....
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    как?
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      если A - булева матрица смежности

      FOR(k, n) FOR(i, n) FOR(j, n) a[i][j] |= a[i][k] && a[k][j];

      теперь упакуем строки матрицы в массивы unsigned int, и последний цикл будем делать в 32 раза быстрее

      unsigned a[N][N / 32 + 1];

      FOR(k, n) FOR(i, n) if (BitIsOne(a[i][k / 32], k % 32))  FOR(j, n / 32 + 1) a[i][j] |= a[k][j];

      → Ответить