P5425 [USACO19OPEN] I Would Walk 500 Miles G

Farmer John 想要将他的编号为 $ 1 \ldots N $ 的 $ N $ 头奶牛（ $ N \leq 7500 $ ）分为非空的 $ K $ 组（ $ 2 \leq K \leq N $ ），使得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛 $ x $ 和奶牛 $ y $ （其中 $ 1 \leq x

无

无

在这个例子中，奶牛 $1$ 和奶牛 $2$ 愿意为了见面走 $2019201817$ 英里。奶牛 $2$ 和奶牛 $3$ 愿意走 $2019201685$ 英里。奶牛 $1$ 和奶牛 $3$ 愿意走 $2019201769$ 英里。所以，将奶牛 $1$ 单独分为一组，奶牛 $2$ 和奶牛 $3$ 分为一组，$M = \min(2019201817, 2019201769) = 2019201769$（这是我们在这个问题中能够达到的最佳结果）。