[BOJ] 백준 10021 - Watering the Fields

문제 링크

www.acmicpc.net/problem/10021

10021번: Watering the Fields

 

풀이

기본적인 최소 스패닝 트리 문제입니다.

코스트가 $c$이상인 간선만 모아 최소 스패닝 트리를 만들어줍시다.

 

크루스칼에서 union한 횟수가 $n-1$이 되지 않으면 트리를 만들 수 없는 경우입니다.

 

 

정답 코드

#include <bits/stdc++.h>
 
#define TEST int _tt; cin >> _tt; while(_tt--)
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
#define rmDup(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define mem(v, e) memset((v), (e), sizeof((v)))
#define initme(p, n) for(int _i=0; _i<(n)+1; (p)[_i]=_i, _i++)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vs = vector<string>;
using vd = vector<double>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvpii = vector<vpii>;
using vvpll = vector<vpll>;
using vvs = vector<vs>;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3fLL;
 
pll p[2222];
int par[2222];
vector<pair<ll, pii>> edges;
ll n, c;
 
int find(int x) {
    if (par[x] == -1) return x;
    return par[x] = find(par[x]);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> p[i].ft >> p[i].sd;
        for (int j = 0; j < i; j++) {
            ll cost = (p[i].ft - p[j].ft) * (p[i].ft - p[j].ft) + (p[i].sd - p[j].sd) * (p[i].sd - p[j].sd);
            if (cost >= c) {
                edges.emplace_back(cost, make_pair(i, j));
            }
        }
    }
    sort(all(edges));
    mem(par, -1);
    ll ans = 0;
    int cnt = 0;
    bool fin = false;
    for (auto &e: edges) {
        ll cost = e.ft;
        auto[u, v] = e.sd;
        u = find(u);
        v = find(v);
        if (u != v) {
            ans += cost;
            par[u] = v;
            if (++cnt == n - 1) {
                fin = true;
                break;
            }
        }
    }
    if (fin) cout << ans;
    else cout << "-1";
}