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

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

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

15 лет назад, скрыть # |
 
Проголосовать: нравится -9 Проголосовать: не нравится
ухты .. интересная задача , прямо самому захотелось узнать решение!
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А ограничения есть?
→ Ответить
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -9 Проголосовать: не нравится

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

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

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

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

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