Как понять условие задачи?

Question

[Proshka17]

Добрый день!
Есть задача
Код:

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <functional>
#include <string>
#include <algorithm>
using namespace std;



class Sol {
public:
  long long max = -1;


};

int main() {
  ifstream f("input.txt");
  Sol s;
  string nodes;
  string rebr;
  f >> nodes;
  f >> rebr;
  for (long long i = 0; i < stoll(rebr); i++) {
    string fr;
    string to;
    string we;
    f >> fr;
    f >> to;
    f >> we;
    if (stoll(we) > s.max) s.max = stoll(we);
  }
  cout << s.max;
 

  return 0;
}

Answer 1

[Mercury13]

Что вы не поняли в решении: вы оптимизируете «чёрную» половинку графа, забыв, что самое малое ребро может быть в «белой».

ДЛЯ КАЖДОЙ ВЕРШИНЫ: ук-ль на «начальника» + флаг инверсии. Если у вершины нет начальника — то указывает в null.
ДИРЕКТОРОМ назовём вершину, у которого нет начальников. Считаем также, что у директора флаг инверсии всегда false.

Заведём функцию getInfoNonDestructive, она возвращает структуру из двух элементов. Во-первых, это директор (никогда не null!!). Во-вторых, это цвет — XOR флагов инверсии от самóй вершины до директора.

Функция getInfo вызовет getInfoNonDestructive, а затем проведёт ОПТИМИЗАЦИЮ СТРУКТУРЫ: ЕСЛИ вершина имеет начальника, ТО: начальник вершины := директор, флаг инверсии вершины := цвет вершины.

СЛИЯНИЕ фирм происходит так. Директор фирмы становится подчинённым кому-то из членов другой фирмы.

ИЗНАЧАЛЬНО для всех вершин начальник — null, флаг инверсии — false. То есть каждая вершина белая и сама себе директор.
РЕШЕНИЕ: Отсортируем рёбра в порядке возрастания.
Для каждого ребра…
• Находим информацию о вершинах — концах ребра.
• Если директор один и цвета разные — ничего не делаем.
• Если директор один и цвет один — выводим вес этого ребра как ответ.
• Если директора разные — сливаем фирмы. Подкручиваем флаг инверсии того директора, который исчез, так, чтобы цвета вершин — концов ребра были разные. Хотя бы так.

VertexInfo info1 = getInfo(vertex1);
VertexInfo info2 = getInfo(vertex2);
if (…) {
  info1.director->superior = info2.director;
  VertexInfo info1new = getInfoNonDestructive(vertex1);
  if (info1new.color == info2.color)
    info1.director->inverseFlag = !info1.director->inverseFlag;
}

ВНИМАНИЕ, без оптимизации структуры сложность с «чуть более O(N)» превращается в N²! Но конкретно в этом месте важно получить инфу без разрушений — временно запрещается кого бы то ни было выводить из-под старого директора, пока не выставим ему флаг инверсии цвета.

Если рёбер не осталось — перед нами двудольный граф, такого по условию не бывает.

(такая структура данных, только без флага инверсии, называется, «система непересекающихся множеств»).

ТЕОРИЯ. Начиная от самых «маленьких» рёбер, начинаем раскрашивать вершины в разные цвета. Если в какой-то момент это не удалось (цвета уже одинаковые) — выводим это ребро как ответ. Если соединяются два раскрашенных «островка» (в нашей терминологии «фирмы») — возможно, один из островков придётся инвертировать, и надо наладить инверсию так, чтобы она не захватила весь островок (судя по цифре 10⁵, от нас ожидают сложность N log N, а не N²). Поскольку соединение кусков графа рёбрами и подсчёт компонент связности — это самая настоящая система непересекающихся множеств, я попытался приделать к этой самой СнПМ раскраску, не повышающую общую сложность (амортизированные почти что O(1) за транзакцию).

Попробуй доказать самостоятельно, что данная система не зависит от того, в каком порядке оказались рёбра с одинаковым весом.

И кончайте на чужом буе в рай въезжать!

Comments

[Proshka17]

Добрый день!
Большое спасибо за такой развернутый ответ!
В примере к заданию есть такой пример:
4 5
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
И ответом является 2.
Визуализация графа
Из примера следует, что нам нужно максимизировать не минимальное ребро из двух подмножеств, а сделать подмножество чемпион, в котором должно быть максимальное ребро, иначе ответом была бы 1.
Здесь получается, что в одно множество входят вершины вокруг двойки, а в другое все остальные вершины. Тогда не понятно, почему мы не можем всегда разбивать граф на максимальное ребро и на все остальное. Судя в по всему, в примере так и сделано.

[Mercury13]

Начинаем…
12 → 1 белая, 2 чёрная
23 → 3 белая
34 → 4 чёрная
41 → порядок, ничего не делаем
24 → противоречие, выводим 2

[Mercury13]

Proshka17,

Тут просто так совпало. А теперь давайте возьмём тот же пример и ребру 41 дадим вес 3. Ничего же, сцуко, не изменится, и придётся цацкаться с рёбрами единичного веса, а потом нарваться на противоречие с ребром 24 и вывести ответ 2?

[Proshka17]

Mercury13, Получается алгоритм выведет 2 как ответ, но разве не 3 является ответом? Мы же можем разбить граф на (1)(4) и (2)(3) вершины и тогда в левом подграфе минимальным ребром будет 3

[Mercury13]

Proshka17, А в правом — 1.

[Proshka17]

Mercury13, Понял, спасибо. Сначала немного не так трактовал условие

[Proshka17]

Mercury13, Добрый день!
и прочитал про «система непересекающихся множеств», но не совсем понял зачем XOR флагов инверсии. Не могли бы вы пожалуйста объяснить зачем нужен XOR флагов?

[Mercury13]

Proshka17, Бывает, что очередное ребро приводит к слиянию двух раскрашенных «островков». И вдруг оказывается, что один из них нужно было красить наоборот: белое должно быть чёрным, а чёрное — белым. Как перекрасить целый остров за O(log N) или даже быстрее?

[Mercury13]

Proshka17, По факту у нас все вершины выкрашены в белый цвет, а «очерняются» они именно этими флагами.

[Mercury13]

Уточню: АМОРТИЗИРОВАННОЕ O(log N). То есть некоторые транзакции могут тормозить, но в общем сложность логарифмическая или быстрее.

[Proshka17]

Mercury13, Все работает, спасибо за помощь!

Answer 2

[jcmvbkbc]

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

Контрпример: квадрат, верхнее ребро -- 2, боковые -- 1, нижнее -- 0. В терминах входных данных для задачи:

4 4
0 1 2
1 2 1
2 3 0
3 0 1

Если разбивать твоим алгоритмом, то в одно множество попадают две верхние вершины, во второе -- две нижние. Тогда "ребро минимального веса, соединяющее вершины из одного множества" -- это ребро соединяющее две нижние вершины (2 3), его вес -- 0.
Но если разбить граф на две левые вершины (3 0) и две правые (1 2), то "ребро минимального веса, соединяющее вершины из одного множества" имеет вес 1, что лучше, чем 0.

Answer 3

[longclaps]

Ты вот в чем ошибся: максимальное ребро могло быть мостом, и выкусив его, ты развалил бы граф на минимум два подграфа, плюс пара инцидентных ребру першин будет третьим подграфом - а это перебор.
Поэтому просто перебери рёбра в порядке убывания, какое не окажется мостом - то и будет решением.

Comments

[Proshka17]

Добрый день!
Вот только не понятно как разделить граф на два подмножества

[longclaps]

Proshka17, да что ж такое: перебираем все ребра по убыванию, выкусываем их (с вершинами), если граф не развалился (проверяем на связность) - эти две вершины и составляют одно из подмножеств. Развалился - поехали дальше.

[Proshka17]

longclaps, Так не получится:
Контрпример: квадрат, верхнее ребро -- 2, боковые -- 1, нижнее -- 0.
Возьмем верхнее ребро, тогда граф останется связным - значит две верхние вершины это одно подмножество, а две нижние другое. Теперь ответим на вопрос в условии задачи, выберем минимальное ребро из двух подмножеств и получим ответ 0.
Если же разобьем квадрат на две правые и две левые вершины, то ответом будет 1.

[longclaps]

Разбейте вершины графа на два не пустых множества так, чтобы ребро минимального веса, соединяющее вершины из одного множества, имело максимально большой вес.

Теперь ответим на вопрос в условии задачи, выберем минимальное ребро из двух подмножеств

Proshka17, мне не показалось, что это одно и то же. Мне показалось, нужно организовать одно подмножество - чемпион.
Впрочем, я подумаю и над задачей в вашей трактовке.

[Proshka17]

longclaps, Добрый день!Посмотрел в примерах к заданию такой пример:
4 5
1 2 1
2 3 1
3 4 1
4 1 1
2 4 2
И ответом является 2. Так уж вы были праву на счет трактовки условия. Но предложенное вами решение не решает задачу. Если в приведенном мною примере если вырезать ребро весом 2 и его вершины, то мы разобьем граф на три куска, но есть разбиение графа на 2 подмножества, где ребро весом 2 будет максимальным. Если поделитесь какими-нибудь идеями по поводу решения, буду очень признателен

[longclaps]

Proshka17, видно, я тоже невнимательно читал.

Разбейте вершины графа на два непустых множества

На два множества, а не два связных подграфа.
Видно же, что изъятие ребра-двойки развалит граф, а иначе никак.
Выходит, нужно просто делить на пару вершин при максимальном ребре - и на все оставшиеся.

[Proshka17]

Думаю что под подмножествами имелись ввиду связные графы, иначе можно просто взять максимальное ребро, а все остальное засунуть во второе множество.Такой вариант не сработал.

[longclaps]

Proshka17, но в твоём-то примере так не получается! Если ты добавишь к вершинам ребра-двойки любую из оставшихся - ты получишь ответ 1.

[Proshka17]

longclaps, Ну да, получается в данном примере, в одно множество входят вершины вокруг максимального ребра, а другое все остальное. Тогда не понятно, почему максимальное ребро - это не всегда правильный ответ?

[longclaps]

Proshka17, этого я не знаю )