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

Автор Na2a, история, 9 лет назад, По-русски

Помогите с задачей D отсюда.

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

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Нужно научиться разбивать граф на 2n - 1 1-факторов (т.к. мы можем получить a + b-фактор как объединение a-фактора и b-фактора). А это делается совсем просто: i-ый по счету 1-фактор будет состоять из ребер (a, b) таких, что , а b = (a + i), если a + b ≤ 2n и b = (a + i - 2n), если a + b > 2n.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Спасибо большое!

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Только мое решение неправильное. Разбивать граф на 1-факторы нужно как-то по-другому.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Ок, попробую разобраться в чужих решениях. Идею словил.