Учитывая стоимость между n элементами, где стоимость [i] [j] обозначает стоимость между элементами i и j, нам нужно разделить n элементов на k непустых групп так, чтобы, если 2 элемента принадлежали к одной группе, стоимость между парами становится 0. Учитывая деление, пусть M - минимальная стоимость 2 пар, не принадлежащих к одной группе. Мне нужно найти максимально возможное M. (деление нам не дано, нам нужно найти оптимальное деление, а затем найти максимально возможное M)
Я подумал о сортировке всех затрат [i] [j], а затем о бинарном поиске по ним. Допустим, мы находимся в позиции x в отсортированном массиве, где стоимость равна M, и это обозначает грань между (i, j). Мы предполагаем, что это максимально возможное значение M. Итак, мы знаем, что i-й элемент и j-й элемент должны находиться в разных группах. Затем мы получаем bfs из i-го элемента и добавляем все смежные элементы, стоимость которых меньше текущей M. Это будет в текущей группе. Мы продолжаем bfsing, пока у нас не закончатся элементы в этой группе. Затем мы переходим к нашей следующей группе и снова делаем bfs из j-го элемента. Если мы сталкиваемся с элементом, который уже находится в предыдущей группе, но стоит меньше, чем M, с элементом из текущей группы, мы либо возвращаем false, либо пытаемся объединить две группы. В этой части я не уверен насчет
примером будет, если n = 3, k = 2 и стоимость [1] [2] = 17, стоимость [2] [3] = 15, стоимость [1] [3] = 16
мы можем поместить элемент 1 в группу 1 и элемент 2 в группы 2 и 3. Максимальное значение M в этом случае будет min (стоимость [1] [2], стоимость [1] [3]) = 16
Это лучшее, что можно сделать