Теория графов Алгоритм

Question

Данная проблема является

Учитывая лес с п вершинами, добавить края, чтобы превратить его в дерево с минимального диаметра. Я пробовал много подходов, но ни один из них не прошел системные тестовые примеры. Пожалуйста, предложите какой-то алгоритм для решения этой проблемы.

Это ссылка редакции ncpc.idi.ntnu.no/ncpc2015/ncpc2015slides.pdf Проблема заключается в присоединении к сетям. Я не могу понять решение, предложенное в редакционном

Update:

https://www.quora.com/What-is-the-solution-for-Dreaming-on-IOI-2013

Эта ссылка обеспечивает лучшее объяснение для решения упомянутых в редакционном

Answer 1

эксцентриситет вершины v , обозначенный как ecc(v), определяется как ecc(v):=max_u d(u,v), т. е. как расстояние до самой отдаленной вершины на графике. A центр графа G - любая вершина v, для которой ecc(v)=min_v max_u d(u,v), т. Е. Центр - это вершина, которая минимизирует эксцентриситет.

Если объединить два дерева (из разных компонент связности), T1 и T2, положив край между их центрами c1 и c2, вы получите это дерево T с diam T = max(diam T1, diam T2, 1+rad(T1)+rad(T2)).

Правильность подхода ниже должна быть очевидна из этих свойств.

Вот одна идея для алгоритма, с верхней части моей головы:

• пусть T1, T2 ..., Tk быть деревья, составляющие леса.
• вычислить a center vertexci для каждого из деревьев Ti.
• подключить компоненты путем разумного разметки краев между центрами.

Конечно, проблема в том, как умело решить последнюю пулю. Интуитивно я предлагаю вам сначала связать treest с самыми большими диаметрами (а затем обновить диаметр нового дерева и вычислить центр нового дерева). Возможно, что-то вроде этого:

в то время как очередь приоритет содержит более одного дерева сделать

• пусть T1 и T2 быть деревья с наибольшим диаметром; пусть c1 и c2 будут их центрами;
• connect c1 и c2 для образования нового дерева T;
• вычислить новый центр cT, вычислить diam T и поставить T обратно в очередь приоритетов (которая может быть максимальной кучей, использующей диаметр в качестве ключа).

сделано

Update. Я не уверен, присоединиться ли сначала к деревьям с наибольшим диаметром сначала или наоборот (сначала деревья с наименьшим диаметром). Но теперь очень легко сделать эскиз доказательства (как только вы выясните, какой путь), что это правильный путь.

Обновление. Математика, безусловно, проходит, если вы подключаете наибольшую первую (как предлагается в PDF).