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

ПОМОГИТЕ РЕШИТЬ ЗАДАЧУ BOI2011.T4
Автор ilyaraz, 13 лет назад, По-русски
На самом деле я тут наткнулся на очень красивую задачу, но, к сожалению, увидел условие вместе с решением. :( За какое наилучшее время вы сможете ее решить?

Задан связный ненаправленный граф (n вершин, m ребер), на каждом ребре которого два неотрицательных веса: A и B. Нужно найти остовное дерево, которое минимизирует произведение суммарных A-весов и суммарных B-весов.
  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
ухты .. интересная задача , прямо самому захотелось узнать решение!
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    "решение", "задач"
    Уж не Вы ли написали оригинальное сообщение?
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А ограничения есть?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Веса произвольные вещественные. Алгоритм должен работать за полиномиальное по n и m время.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Мда, вовремя ты это написал. Я уже почти дописал комментарий с полиномиальным по сумме (целых) весов решением :) Но с такими весами задача выглядит ещё интереснее :)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, задача отличная. И в то же время решаемая. Один человек на балканской олимпиаде ее порубил.
        → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

они не похожи случаем?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Можно поконкретней задачу сформулировать?

на ребре i есть число A[i] и число B[i], нужно найти подмножество рёбер S такое что рёбра из него образуют остовное дерево, и минимизирует (сумма A[i] по всем i из S) *  (сумма B[i] по всем i из S)  ?

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Это задача Т5, а не Т4 :о)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ну так что, неужели никто не придумал? :( А кому-нибудь интересен разбор задачи?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    К сожалению непридумал и поэтому в итоге нагуглил разбор задачи =). Задача действительно интересная.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, красивая идея -- рассмотреть выпуклую оболочку решений.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А если веса вещественные, то почему на выпуклой оболочке будет не много решений?
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Вершина выпуклой оболочки минимизирует некоторый линейный функционал. То есть для каждой вершины существует число s такое, что данное дерево является обычным минимальным остовным для веса sA + (1 - s)B. То есть нужно вычислить обычные MST для всех s. А таких, понятно, не больше, чем m^2, так как если мы будем менять s, то MST может поменяться только тогда, когда два каких-то ребра уравняются.
          → Ответить
          • 13 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Итого, если реализовать это наивно, то получится сложность . Можно ли быстрее?
            → Ответить