Meadow 草地的问题

Question

Description

As you have probably guessed, we are talking about an ordinary meadow with lot of flowers scattered all around it. Flying between them, landing on them and taking off from them are numerous industrious bees, collecting raw material known as pollen used to produce honey in their hives. Since lives and prosperity of the bee community depends heavily on it, every flower needs to be visited to collect as much pollen as possible.

Maya is the bee who has to make a scheduling list according to which the bees will visit all the flowers on the meadow. A scheduling list consists of several sets of flowers (their positions, actually). Each bee is given one set and it has to visit all the flowers from it in an arbitrary order. Each flower can be visited arbitrary many times. The weight of a sequence of flowers is the largest distance between two successive flowers in the sequence. The weight of a set of flowers is the minimal weight of all sequences of flowers from the set. A bee with given set of flowers will always plan its flight according to the sequence of all flowers from the set with minimal weight. The weight of a scheduling list is the maximal weight of all sets in the scheduling list.

Write a program that will help Maya to find a scheduling list with the lowest weight.
Input

The first line of the input consists of two natural numbers F and B; 1 <= F <= 2000, 1 <= B <= F, F is the number of flowers in the meadow and B is the number of bees available for collecting pollen.

Each of the next C lines contains two natural numbers X and Y, 1 <= X,Y <= 10000, the coordinates of a flower.
Output

The first and only line of the output file should contain the minimal possible weight of a scheduling list for the data given in the input file as described above. The result should be rounded to two decimal places.
Sample Input

3 2
1 1
2 3
3 2
Sample Output

1.41

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# 读取数据
f <- readLines("meadow.txt")
F <- as.integer(f[1])
B <- as.integer(f[F+1])

# 构建边的矩阵
G <- matrix(0, nrow = F + 1, ncol = F + 1)
for(i in 1:(F-1)) {
  G[i, i+1] <- 1
  G[i+1, i] <- 1
}
for(j in 1:F) {
  for(k in 1:F) {
    if(abs(G[j,k]) < 1e-5) {
      G[j,k] <- 1
      G[k,j] <- 1
    }
  }
}

# 构建邻接表
adj <- matrix(0, nrow = F + 1, ncol = F + 1)

for(i in 1:F) {
  adj[i,i] <- -i
  for(j in 1:i) {
    adj[i,j] <- -j
    adj[j,i] <- -j
  }
}

# 构建邻接矩阵
distances <- matrix(0, nrow = F + 1, ncol = F + 1)
for(i in 1:F) {
  distances[i,i] <- 0
  for(j in 1:F) {
    distances[i,j] <- inf
    for(k in 1:F) {
      dist <- abs(distances[i,k] + G[i,j]*G[k,j])
      if(dist < distances[i,j]) {
        distances[i,j] <- dist
      }
    }
  }
}

# 构建优先队列
pq <- vector(length = F + 1)
for(i in 1:F) {
  pq[[i]] <- c(-distances[i,F], i)
}

# 按照优先级从大到小排序
sort(pq)

# 初始化结果向量
result <- rep(NA, F + 1)
result[F] <- 0

# 遍历所有可能的路径
for(i in 1:F) {
  for(j in 1:tail(pq[[i]], 1)) {
    result[i] <- max(result[i], j)
    pq[[i]] <- c(pq[[i]][,-1], j)
  }
}

# 输出结果
print(round(sum(result), 2))