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

TJU 3783 Cards
Автор MarioYC, 13 лет назад, По-английски

Hi everyone, so I found this problem today, and it seems like a really obvious bipartite matching, but I've been getting TLE in it. Is there some faster way to solve it?

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

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

O(VE) bipartite matching algorithm obviously gets TLE on dense graph with such limits. I think solution which runs in O(sqrt(v) * E) will pass. For example you can use "Hopcroft–Karp algorithm".

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

    Sorry, forgot to say I used Hopcroft-Karp.

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

      Strange... Show your code, maybe i can help. Solution with O(N ^ 2.376) exists, but i think Hopcroft-Karp must pass.

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

        Here it is: http://pastebin.com/3RH9u4SN

        → Ответить
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Your algorithm works in O(VE) time and it isn't Hopcroft-Karp. Just try this testcase: 500 500

          2 2 2 2 2 ... (500 times)

          2 2 2 2 2 ... (500 times)

          Copy this a few times and then add "0 0". Your algorithm will work more then 5 seconds (and will get TLE).

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

            Thanks, I found the mistake, I was using the || operator instead of |= when updating the variable change. With this change it still isn't Hopcroft karp because i'm not taking shortest paths, but that only makes it a bit slower.

            → Ответить
»
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Dinnic works here, my solution accepted in 4.86 seconds.

→ Ответить