Mercury13, Добрый день!
и прочитал про «система непересекающихся множеств», но не совсем понял зачем XOR флагов инверсии. Не могли бы вы пожалуйста объяснить зачем нужен XOR флагов?
Mercury13, Получается алгоритм выведет 2 как ответ, но разве не 3 является ответом? Мы же можем разбить граф на (1)(4) и (2)(3) вершины и тогда в левом подграфе минимальным ребром будет 3
Добрый день!
Большое спасибо за такой развернутый ответ!
В примере к заданию есть такой пример:
4 5
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
И ответом является 2. Визуализация графа
Из примера следует, что нам нужно максимизировать не минимальное ребро из двух подмножеств, а сделать подмножество чемпион, в котором должно быть максимальное ребро, иначе ответом была бы 1.
Здесь получается, что в одно множество входят вершины вокруг двойки, а в другое все остальные вершины. Тогда не понятно, почему мы не можем всегда разбивать граф на максимальное ребро и на все остальное. Судя в по всему, в примере так и сделано.
longclaps, Ну да, получается в данном примере, в одно множество входят вершины вокруг максимального ребра, а другое все остальное. Тогда не понятно, почему максимальное ребро - это не всегда правильный ответ?
Думаю что под подмножествами имелись ввиду связные графы, иначе можно просто взять максимальное ребро, а все остальное засунуть во второе множество.Такой вариант не сработал.
longclaps, Добрый день!Посмотрел в примерах к заданию такой пример:
4 5
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
И ответом является 2. Так уж вы были праву на счет трактовки условия. Но предложенное вами решение не решает задачу. Если в приведенном мною примере если вырезать ребро весом 2 и его вершины, то мы разобьем граф на три куска, но есть разбиение графа на 2 подмножества, где ребро весом 2 будет максимальным. Если поделитесь какими-нибудь идеями по поводу решения, буду очень признателен
longclaps, Так не получится:
Контрпример: квадрат, верхнее ребро -- 2, боковые -- 1, нижнее -- 0.
Возьмем верхнее ребро, тогда граф останется связным - значит две верхние вершины это одно подмножество, а две нижние другое. Теперь ответим на вопрос в условии задачи, выберем минимальное ребро из двух подмножеств и получим ответ 0.
Если же разобьем квадрат на две правые и две левые вершины, то ответом будет 1.
