AK
Size: a a a
2020 July 08
Y
окей спасибо)
Y
есть задача к тому же графу такая:
Y
Для сети потока и потока из задачи 7 замените все ребра
в остаточной игре, случайно с вершины D.
в остаточной игре, случайно с вершины D.
Y
Пример ответа: D->F: 100, D->E: 200, B->D: 300, (...)
2020 July 09
AT
Похоже это какая-то проблема столетия или тысячелетия https://cs.stackexchange.com/questions/128146/find-two-disjoint-set. Никто не знает ответа :(
AT
И это ладно: на стековерфлоу никто не знает — оно понятно, но в этом-то чате полюбому кто-то знает!)
AT
где ещё можно спросить? на реддите может быть есть место? Или дискорд-канал какой-то отзывчивый?
Д🍋
Странно конечно
Если никто не знает
То может она и не возникает обычно? Те обходные пути/другие решения есть
Если никто не знает
То может она и не возникает обычно? Те обходные пути/другие решения есть
Д🍋
Если это часть задачи конечно
AT
Ну формулировка предельно простая. Полюбому какие-то части каких-то задач сводятся к этому
AT
"дано множество путей на полном графе, есть ли в этом множестве хотя бы пара непересекающихся путей"
В
Похоже это какая-то проблема столетия или тысячелетия https://cs.stackexchange.com/questions/128146/find-two-disjoint-set. Никто не знает ответа :(
Не понятна трактовка задачи, почему ищутся пересечения элементов, а не подмножеств?
mq
Похоже это какая-то проблема столетия или тысячелетия https://cs.stackexchange.com/questions/128146/find-two-disjoint-set. Никто не знает ответа :(
так пусть у вас один элемент принадлежит всем множествам в А и Б, тогда ответа нет
AT
так пусть у вас один элемент принадлежит всем множествам в А и Б, тогда ответа нет
ну это патологический случай. Можно наложить условие. что все элементы в A уникальны и все элементы в Б тоже уникальны
mq
извиняюсь, не прочитал до конца..
AT
а, хотя это ортогонально
Д🍋
так пусть у вас один элемент принадлежит всем множествам в А и Б, тогда ответа нет
Там мб пересечение все же не элемент а ребро/чата пути
Д🍋
Тогда нормально
mq
мб 3sum попробовать к ней свести?