MST를 써볼까나?

문제

Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 <= N <= 2000).

Each field i is described by a distinct point (xi, yi) in the 2D plane, with 0 <= xi, yi <= 1000. The cost of building a water pipe between two fields i and j is equal to the squared Euclidean distance between them:

(xi - xj)^2 + (yi - yj)^2

FJ would like to build a minimum-cost system of pipes so that all of his fields are linked together – so that water in any field can follow a sequence of pipes to reach any other field.

Unfortunately, the contractor who is helping FJ install his irrigation system refuses to install any pipe unless its cost (squared Euclidean length) is at least C (1 <= C <= 1,000,000).

Please help FJ compute the minimum amount he will need pay to connect all his fields with a network of pipes.

문제 해석

농부 존은 배수 시스템을 만들어서 N개의 필드에 물을 흘려보낼려고 한다. N개의 필드는 서로 연결이 되어있기만 하면, 물을 수월하게 흘려보낼 수 있다.

필드와 필드 사이의 거리는 (xi - xj)^2 + (yi - yj)^2 이고, 적어도 C 이상의 거리를 가진 필드의 짝만 사용한다고 치자!

그렇게 했을 경우, 모든 필드를 연결하는 최소의 비용은 몇인가?

입력

  • Line 1: The integers N and C.
  • Lines 2..1+N: Line i+1 contains the integers xi and yi.

출력

  • Line 1: The minimum cost of a network of pipes connecting the fields, or -1 if no such network can be built.

문제 아이디어

  • 모든 필드를 연결하는 최소의 간선 수는 (N-1) 임을 알 수 있다.
  • 간선의 길이가 C 이상인 간선의 갯수가 N-1 보다 작으면 , -1을 리턴함을 알 수 있다.
  • C 이상의 길이를 만족하는 것 중에서, 최소의 간선비용을 찾아야 하므로 힙 자료구조를 쓰던가 소팅해서 최소의 비용부터 뽑아내야 함을 알 수 있다.
  • 결국 이 문제는 MST를 사용해야하는 문제이다. MST에 대해 모른다면 여기 를 통해 보면 된다.
    • MST의 제일 큰 요점은 간선을 추가했을 때 사이클을 형성하느냐? 이다.
    • MST를 푸는 가장 흔한방법은 Union Find 알고리즘을 사용하는 것이다. 이것에 대해 알고싶다면 여기 를 통해 보면 된다.

문제 풀이

bj10021

Code