[BOJ] 10021 : Watering the Fields

문제 링크

https://www.acmicpc.net/problem/10021

10021번: Watering the Fields

Farmer John 을 도와서 모든 field에 물을 주기위해서 필요한 최소비용을 출력하자.

풀이

일단 영어문제라서 문제를 정확히 해석하는게 어려웠다.

각 필드를 노드처럼 생각하고 모든 필드가 이어지도록 해야한다. 그리고 두 필드사이의 파이프 설치 비용은 주어진 공식 (xi - xj)^2 + (yi - yj)^2 를 이용해서 구한다.

하지만 각 파이프를 설치할 때 설치하는 사람이 최소 비용 C 보다 설치비용이 낮다면 그 구간에는 설치를 해주지 않는다.

모든 노드를 최소 비용으로 연결시켜야 하므로 "최소 스패닝 트리"를 사용한다. 모든 노드 사이에 설치비용을 구해서 C보다 크거나 같다면 우선순위 큐에 넣는다.

이렇게 해서 최소 스패닝 트리를 만들어주면 되는데, 만약 모든 노드를 연결하지 못한다면 -1을 출력해주면 된다. 즉 모든 노드의 Parent가 같으면 비용 출력, 같지 않으면 -1을 출력하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 2000 + 5;
int N, C;
vector<pair<int,int>> Position;
int Parent[MAX_N];
 
int Find(int X) {
    if (Parent[X] == X)
        return X;
    else return Parent[X] = Find(Parent[X]);
}
 
void Union(int x, int y) {
    int parent_x = Find(x);
    int parent_y = Find(y);
    Parent[parent_x] = parent_y;
}
 
int get_cost(int A, int B) {
    return (pow(Position[A].first - Position[B].first, 2) + pow(Position[A].second - Position[B].second, 2));
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> C;
    for (int i = 0; i <= N; i++)
        Parent[i] = i;
    for (int i = 0; i < N; i++) {
        int X, Y;
        cin >> X >> Y;
        Position.push_back({ Y,X });
    }
    Priority_queue pq;
    for (int i = 0; i < Position.size() - 1; i++) {
        for (int j = i + 1; j < Position.size(); j++) {
            int cost = get_cost(i, j);
            if (cost < C) continue;
            pq.push({ cost,{i,j} });
        }
    }
    int ans = 0;
    while (!pq.empty()) {
        int cost = pq.top().first;
        int Node1 = pq.top().second.first;
        int Node2 = pq.top().second.second;
        pq.pop();
        if (Find(Node1) != Find(Node2)) {
            ans += cost;
            Union(Node1, Node2);
        }
        else continue;
    }
    bool chk = true;
    int Parent_zero = Find(0);
    for (int i = 1; i < N; i++)
        if (Parent_zero != Find(i)) {
            chk = false;
            break;
        }
    if (chk)
        cout << ans << "\n";
    else cout << "-1\n";
    return 0;
}