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

Timus. 1774 Парикмахер армии магов.
Автор BearPlu, 13 лет назад, По-русски

Прошу помочь с идеей решения этой задачи. Я строю сеть. Вершинами являются маги, моменты времени, сток и исток. Нахожу максимальный поток  в сети, что дает мне ответ "Yes" или "No". Но не могу восстановить ответ, т.к. матрица потока не дает ответ.

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

13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
задача решается без потока, жадно
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится
    После соревнования были добавлены тесты, которые ломали жадное решение.
    Сейчас проходил у меня только поток.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      лололо, у меня акцептед до сих пор =)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        У всех акцептед :)
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Хе. Только что переотправил свой код c контеста и получил WA#39.
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        дело в том, что посылки, которые были на соревновании, не перепроверяются)))
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится
          мы говорим о тимусянских задачах? =)

          так вот, мне стабильно несколько раз в год приходят письма от [email protected] с темой New judgements, где меня радуют, что нашлись хорошие тесты к задаче #N и теперь старое решение получает WA/TL на тесте с номером, близким к трёхзначному

          все посылки, которые отправлялись на соревнованиях, перепроверяются, но результаты контеста остаются неизменными

          в данном случае имеет место быть именно отсутствие теста против моего решения
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            попробуй отправить старое решение сейчас
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится -12 Проголосовать: не нравится
              да, и правда WA :D

              в таком случае нужно поздравить тимус с фэйлом и ждать справедливого режаджа, который, почему-то, не случился вовремя
              → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            дело в том, что я в рейтинге авторов какой-то задачи видел решения на последнем месте с временем работы около секунды, хотя ограничение по времени там стоит 0.25 секунды. вот поэтому я решил, что перепроверки решений с соревнований нет))
            → Ответить
            • 13 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              например вот http://acm.timus.ru/rating.aspx?space=1&num=1200&pos=1401

              ограничение времени по задаче 0.25 сек.

              а на последнем месте в рейтинге авторов решение с временем 0.821 сек.))

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

                моё тимусовосприятие перевернулось с ног на голову =)
                → Ответить
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Согласитесь, что не справедливо снимать Accepted, полученный на контесте, прошедшем 9 лет назад.
                → Ответить
                • 13 лет назад, # ^ |
                  ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

                  Мне кажется, что монитор не пересчитывается, а Accepted снимается - единственно ставящий в равное положение вариант.
                  → Ответить
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  что мешает сделать как предложил анонимус? ведь это самое разумное))) 
                  → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      один мой хороший знакомый, который добился неплохих результатов в олимпиадном программировании, в заключении древнего спора о топкодерской задаче сказал замечательную вещь: "и всё равно моё решение верно, и accepted это подтверждает" =)
      → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Я пробовал жадный алгоритм придумать, но он не проходит вот такой тест:
5 2
0 2
0 3
0 5
3 2
3 2

Исправил)))
→ Ответить
13 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится
Не очень понятно. Дело в том, что ответ задачи вы интерпритируете как поток, но при этом из потока не можете восстановить ответ задачи?

P. S.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    С этим и проблема. Не могу из потока восстановить ответ.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится -17 Проголосовать: не нравится
      Как вы строите граф тогда?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Маги соединяются с моментами времени, пропускная способность ребра 1. Исток соединяется с магами, пропускная способность ребра 2. Сток соединяется с моментами времени, пропускная способность k.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится -15 Проголосовать: не нравится
          Разбейте поток на пути (т.е. на потоки объема 1). Путь, проходящий через момент времени t и мага m означает, что в момент времени t маг m стрижется.
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я решал так:

Граф состоит из двух долей. Левая доля - маги (N штук), правая доля - время. От истока ко всем магам идут ребра пропускной способностью 2 (каждого мага надо побрить 2 раза). От каждого мага (вершины левой доли) к вершинам, обозначающим время, идут ребра пропускной способностью 1. Причем только к тем вершинам из правой доли, в которые маг может быть побрит (по входным данным). От каждой вершины правой доли в сток идут ребра пропускной способностью k (в каждый момент времени можно побрить не более k магов).

Теперь в таком графе надо найти поток. Если он будет равен 2*N (каждого мага побрили по 2 раза), то ответ "Yes" , иначе "No". Если ответ положительный, то моменты времени восстановить не сложно. Используемые ребра в матрице смежности будут равны нулю.

Цикл по магам (i)
   Цикл по возможному времени для мага (j)
      Если в матрице смежности на позиции [i][j] находится 0. То именно в этот момент мы побрили   этого мага.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится -23 Проголосовать: не нравится
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не совсем понял момент, когда вы восстанавливаете ответ...
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Начальная матрица смежности. (1, 2, 3 - маги. 7 8 9 - моменты времени (пусть это будет 1,2 и 3 минуты соответственно). k = 2

         S 1 2 3 7 8 9 T
      S 0 2 2 2 0 0 0 0
      1 0 0 0 0 1 1 1 0
      2 0 0 0 0 1 1 1 0
      3 0 0 0 0 1 1 1 0
      7 0 0 0 0 0 0 0 2
      8 0 0 0 0 0 0 0 2
      9 0 0 0 0 0 0 0 2
      T 0 0 0 0 0 0 0 0

      Найден путь S - 1 - 7 - T  ([S][1]; [1][7]; [7][T] получают "- 1"; [T][7]; [7][1]; [1][S] "+1")

         S 1 2 3 7 8 9 T
      S 0 1 2 2 0 0 0 0
      1 1 0 0 0 0 1 1 0
      2 0 0 0 0 1 1 1 0
      3 0 0 0 0 1 1 1 0
      7 0 1 0 0 0 0 0 1
      8 0 0 0 0 0 0 0 2
      9 0 0 0 0 0 0 0 2
      T 0 0 0 0 1 0 0 0

      И т.д.
      В результате часть результирующей матрицы будет равна
        7 8 9
      1 0 0 1
      2 0 1 0
      3 1 0 0
      Означает, что первый маг побрит в моменты 7,8. Второй в - 7,9. Третий в - 8,9. (там где 0 в матрице)
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится -7 Проголосовать: не нравится

        授人以鱼不如授人以渔


        Судя по вопросу, участник плохо понимает, что такое поток, что такое остаточная сеть и как все это работает вообще. Лучше, дайте ему разобраться.
        → Ответить