l
что за вопрос в чате с таким названием?
сам же сказал про топорный способ :) что может быть топорнее
Size: a a a
2020 April 12
2020 April 13
Ш
Всем привет
Ш
Есть идеи как решать такое ? https://acm.timus.ru/problem.aspx?space=1&num=2132
Ш
Ну есть предположения что если в компоненте четное количество ребер то этот граф можно разбить
Ш
Но как доказать правда ли это не знаю
A
что-то мне подсказывает, что это про паросочетания реберного графа
EZ
что-то мне подсказывает, что это про паросочетания реберного графа
++
AL
что-то мне подсказывает, что это про паросочетания реберного графа
А часто рассматриваются графы без ребер?
Ш
что-то мне подсказывает, что это про паросочетания реберного графа
Ого, да очень похож
Ш
спасибо!)
МК
А часто рассматриваются графы без ребер?
Даже граф Дракула с рёбрами
Ш
что-то мне подсказывает, что это про паросочетания реберного графа
не подскажите какой алгоритм почитать
Ш
вроде граф не двудольный
AL
Максим Кавецкий
Даже граф Дракула с рёбрами
Это прям хорошо
Ш
не подскажите какой алгоритм почитать
а все нашел)
A
ну то есть ты понял, что чтобы создать список смежных ребер, этот алгоритм надо применять на двойственном графе
D
Переслано от Dima
Как формально доказать, что в задаче (Leetcode: 1049 Last Stone Weight II), не будет работать жадный алгоритм. Решение через
DP известно, нужно формально найти алгоритм который формирует такие читаемые последовательности на которых не срабатывает Жадный алгоритм из задачи (Leetode: 1046 Last Stone Weight), когда сталкиваются 2 самых крупных камня из массива.