Учитывая стоимость между n элементами, где cost[i][j] обозначает стоимость между элементами i и j, нам нужно разделить n элементов на k непустых групп так, чтобы, если 2 элемента принадлежат одной и той же группе, стоимость между пары становятся 0. Учитывая деление, пусть M будет минимальной стоимостью 2 пар, не принадлежащих к одной и той же группе. Мне нужно найти максимально возможное М. (деление нам не дано, нужно найти оптимальное деление, а затем найти максимально возможное М)
Я думал отсортировать все cost[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(cost[1][2],cost[1][3]) = 16
Это лучшее, что можно сделать
Если нет ограничения на минимальное количество элементов в группе или группы имеют одинаковое количество элементов, то лучше всего поместить все элементы, кроме элемента k-1
, в одну группу, а все остальные группы состоят из одного элемента. Чтобы найти эти k-1
элементы, которые создают k-1
группы, отсортируйте стоимость по убыванию и возьмите первые k-1
появившиеся элементы.